LinkedList Basics
A linked list is a list structure that organizes data in a sequential path. A linked list is a set of separate nodes all of a certain type. Each node on the list holds its own information and a ‘link’ to the next node on the list. Thus, while a linked list is similar to an ArrayList in that there is some sequential nature to the storage of information, it is different in that there are no indices and the data can be stored anywhere in memory, instead of all in the same location.
How it Works...
A LinkedList relies on a set of ListNodes. A ListNode stores data (any reference type variable) and a pointer to the next node in the list. ListNode elements have methods to access and set both the data and the pointer.
When you create a LinkedList, it creates a pointer to a ListNode, somewhere in the memory. That ListNode has a value of null and a pointer value of null (it is not pointing anywhere). When you add the first value to the list, it simply fills in the value of the initial node (the pointer is still null as it has no second element). When a second node is created, the new value goes into the new node and the next pointer of the first node is set to the address of the second node (and so on).
The List Interface
Both ArrayList and LinkedList implement the List interface. This is a common set of functions that are to be included in data structures that store information in some type of ordered list. The list interface includes the following methods:
- add(Object)
- add(index, Object)
- get(index)
- indexOf(Object)
- remove(index)
- set(index, Object)
So, the main functionality for both ArrayList and LinkedList stays the same. Additionally, each structure has its own methods in addition to those provided by the list interface.
The benefit of this interface is that if we stick to using ONLY the methods provided in the interface, we can exchange the data structures and not have to change our code :)
LinkedList Considerations
In terms of storage, a linked list requires not only the value, but also a pointer to a node. However, the size of the list is only bound by the storage available in the computer. And, as these locations do not need to be consecutive, it can utilize small bits of memory that may otherwise go unused.
In terms of speed and access, LinkedLists have a linear run time for retrieval (as opposed to Array and ArrayList which have constant run time due to indexing). On the other hand, Linked Lists provide constant run time for insertion and deletion (while the Array based structures are linear due to the required shifting).