In Java , LinkedList is a generic class that extends the AbstractSequentialList and implements List , Queue , and Deque interfaces. It is a part of the Java Collection API Library. It basically is an implementation of a type of linked list data structure that facilitates the storage of elements. The contents of this storage can grow and shrink at run time as per the requirement. Quite visibly, it is not very different from the other List classes, such as ArrayList. But, the point of difference is in how the list is maintained at the core. The article is an attempt to delineate the concept behind the data structure involved and its implementation in Java in a terse manner.
Figure 1: A one-dimensional array
A one-dimensional array implies that the elements are stored in a consecutive memory location, organized as a linear list where the size must be defined at the outset of its creation. An array of size, say N, is accessed by its index position through 0 to N-1. Therefore, the first element is represented Array[0], while the last element is Array[N-1].
Now, imagine each array location as a separate „node. “ The nodes must be linked in a manner that the next node is accessible from its current node while traversing.
Note that, unlike arrays, the nodes here are not in consecutive memory locations. As a result, there is no way to traverse them consecutively by their indices. Each node must have one or more exclusive parameter that links to the next/previous node.
According to these links arranged, the linked list data structure can be of following types.
Figure 2: The linked list data structure
A singly linked list arranges nodes in a linear fashion where each node is connected to its immediate next node. The last node links to null , which means end of list. Only one-way traversal is possible in this type of list.
Figure 3: A linear transversal
The list is made circular by making the last node point to the first node. The disadvantage of a singly linked list is somewhat overcome here because, once the last node is encountered, the link points again to the first node. The problem of getting lost after reaching the last node in the singly list has now a meaningful pointer whereby it can traverse again from the beginning.
