Types of list collections
Using lists to solve problems
Various list implementations
Comparing list implementations
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
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.
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.
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.
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.
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.
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.