TM

Chapter 15: Lists - Notes

Chapter Scope

  • Types of list collections

  • Using lists to solve problems

  • Various list implementations

  • Comparing list implementations

Lists

  • A list is a linear collection, similar to stacks and queues, but more flexible.

  • Elements can be added or removed at either end or anywhere in the middle of the list.

  • Three types of list collections:

    • Ordered lists

    • Unordered lists

    • Indexed lists

Ordered Lists

  • Elements are ordered by an inherent characteristic (e.g., alphabetical order for names, ascending order for scores).

  • The elements themselves determine their position in the list.

  • Example:

    • Adding an element to an ordered list requires maintaining the order based on the element's characteristics.

Unordered Lists

  • The order of elements is not based on their characteristics.

  • The user determines the order.

  • New elements can be added to:

    • The front of the list.

    • The rear of the list.

    • Inserted after a specific element.

  • Example:

    • Adding elements to the front, rear, or middle of an unordered list.

Indexed Lists

  • Elements are referenced by their numeric position (index) in the list.

  • There is no inherent relationship among the elements.

  • The user determines the order.

  • Indexes are updated every time the list changes.

  • Example:

    • Adding elements shifts the indexes of subsequent elements.

Lists in the Java API

  • The Java API primarily supports indexed lists (and somewhat unordered lists).

  • It does not have classes that directly implement an ordered list.

  • ArrayList and LinkedList classes both implement the List<E> interface.

Standard LinkedList in Java

  • Constructors:

    • LinkedList(): Constructs an empty list.

    • LinkedList(Collection<? extends E> c): Constructs a list containing elements of the specified collection in the order returned by the collection's iterator.

  • Methods:

    • add(E e): Appends the specified element to the end of the list.

    • add(int index, E element): Inserts the specified element at the specified position in the list.

    • addFirst(E e): Inserts the specified element at the beginning of the list.

    • addLast(E e): Appends the specified element to the end of this list.

    • clear(): Removes all elements from the list.

    • get(int index): Returns the element at the specified position in this list.

    • getFirst(): Returns the first element in this list.

    • getLast(): Returns the last element in this list.

    • indexOf(Object o): Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

    • remove(): Retrieves and removes the head (first element) of this list.

    • remove(int index): Removes the element at the specified position in the list.

    • removeFirst(): Removes and returns the first element from this list.

    • removeLast(): Removes and returns the last element from this list.

    • iterator(): Returns an iterator over the elements in this list in proper sequence (for regular lists).

  • A collection class provides an iterator() method that returns an iterator to the start of the collection.

LinkedList Example (LinkedListExample.java)

  • This program demonstrates storing large amounts of data as a collection using LinkedList.

  • LinkedList is a part of collection that constructs a list containing the elements of the specified collection.

  • Iterator methods return values in the order they are stored.

  • add() method: used to insert data in the LinkedList.

  • hasNext() method: returns true if the iterator contains more elements.

  • next() method: returns the next element in the iteration.

  • Methods for inserting and removing data:

    • addFirst(): insert at the beginning

    • addLast(): insert at the end

    • add(): insert at a specified position

    • removeFirst(): remove from the beginning

    • removeLast(): remove from the end

    • remove(): remove from a specified position

  • Methods to retrieve elements:

    • getFirst(): get the first element

    • getLast(): get the last element

    • get(): get the element at a specified position

  • Some methods are in regular List interface. Some are specific to LinkedList.