| | |
One disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertions and deletions. As such, we consider another data structure called a Linked List that addresses some of the limitations of arrays.
A linked list is a recursive data structure that is either empty (null) or a reference to a node that contains a data item and a reference to another node. Through this structure, a linked list creates a sequence of nodes chained together, where each node contains a data item and a reference to the next node.
Below is an example of a node class for a linked list:
class Node {
Item item; // <-- the data to be stored in this node
Node next; // <-- a link to the "next" node
}
The last node has a reference to null. Note, the node class is self-referential. That is to say, the node class contains a reference to itself.
A reference to a linked list could simply be a reference to the first node of that list. That said, one more often encapsulates the reference to the first node of a given linked list as an instance variable (often called head) in some enclosing linked list class, as shown below. (Recall, there are two kind of inner classes: static and non-static. A static inner class cannot refer directly to instance variables or methods defined in its outer class: it can use them only through an object reference.
public class LinkedList<Item> {
private class Node {
Item item;
Node next;
}
// instance variables
private Node head;
...
It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then head is a null reference.
Linked lists and arrays are the two fundamental ways in which sequential data can be stored. There are advantages and disadvantages to both:
Arrays store elements continuously in memory and support indexed access to the items they contain, but suffer from a fixed size.
Linked lists don't have the advantages of their items being stored continuously in memory or supporting indexed access, but the do support dynamic sizing (i.e., we can create and insert additional nodes, as needed). Related to this, they also often have extremely efficient means for inserting and removing elements. These advantages come at a cost, however. Linked lists incur additional memory overhead due to the need to store so many references. Additionally, linked lists do not allow direct access to their individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.
There are many variations on a theme, when it comes to linked lists. The linked list previously described is known as a singly linked list, as each node only keeps a reference to its successor node.
In a doubly linked list is a list that has two references, one to the next node, and another to previous node.
A third variant of a linked list is called a circular linked list, where the last node of the list points back to the first node (or the head) of the list.
Consider the effect of each fragment below on the singly linked list of 4 elements previously described. (Assume the list is restored to its initial state before each line is executed.)
head = head.next; // deletes the first element of the list as
// objects with no references to them
// are subject to garbage collection
head.next = head.next.next; // deletes the second element of the list
// again as objects with no references to
// them are subject to garbage collection
head.next.next.next.next = head; // creates a circular linked list
// in this case, as our initial list
// is only 4 nodes long initially
Original images and some text by Victor S.Adamchik, CMU, 2009; adapted by P. Oser