[Java] LinkedList

An introduction to LinkedList and ArrayList in Java

LinkedList and ArrayList are probably the two most commonly used built-in data structures in Java. Both of them implemented the List interface which extends the interface Collection.

• LinkedList is a double linked list, we can do sequential access and add a new node in the middle of the list in O(1) time, however, it doesn't have a index for random access
• ArrayList is a resizable list, we can do random access in O(1) time, however, when we want to add or delete an element in ArrayList, it can be less performance than LinkedList

The code snippet of an implementation of double linked list

The snippet below shows the LinkedList that I've implemented during the project can be found here

First of all, in order to implement a double linked list, we need to define a node class which stores datad and has a pointer to its previous and next node. Then we have a header node and tail node in MyLinkedList class, which serve as a pointer to point the first and the last node in the list. Alternatively, we can use the header node and tail node as guard nodes whose next and previous point to the first and last node in the list separately. In the same time, we see that, a double linked list has the following basic methods:

• Appends an element to the end of the list

public boolean add(E element ) 

• Add an element to the list at the specified index

public void add(int index, E element )

• Remove a node at the specified index and return its data element.

public E remove(int index) 

• Get the element at position index

public E get(int index)

• Set an index position in the list to a new element

public E set(int index, E element) 

• Return the size of the list

public int size() 

Also we have the toString() method, these methods permit the basic manipulation of a linked list. Compared the linked list that I implemented by myself, the bulit-in LinkedList class in Java is far more complex as it has implemented several other interfaces like the Queue interface. That is to say, when we need a queue structure, we can initialize a queue that contains integer by the following method

Queue<Integer> q = new LinkedList<Integer>()

Then we can use the bulit-in method of queue, like add(E e), peek(), poll() and remove()

Instead, the following declearation of a queue is not correct

Queue<Integer> q = new LinkedList()