One major advantage with using arrays as a data structure is it is always fixed size. Linked lists data structure can solve that storage limit with arrays. Lists have in flavours of singly and doubly. We will consider singly lists here.
Singly linked lists are like a chain. You have the first node and you can keep adding nodes for infinity. One thing is to identify the ends of the chain we have some mechanisms like painting chain ends in different colors.
Basic feature of linked lists
Linked list is composed node nodes.
Each node has to parts.
- First part is to store data(ints, strings or object types).
- Second part is to store a reference to the next node. (Like in the chain example)
First node is called the head node. (This is how we identify the front)
Last node is marked as the node where its next is null which means not references to any node
size can be introduced as a variable to detect lists number of items in any given time.
Image obtained from : http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html
Node declaration in Java (For illustration purposes)
private static class Node<E>
{
private E data;
private Node<E> next;
public Node(E d, Node<E> n)
{
data = d;
next = n;
}
}
Linked List Operations in Java - (For illustration purposes)
Adding a data item from the head of the lists
Process addFirst(e):
newest = Node(e) // New node is created to add first
newest.next = head // created nodes next reference is pointed to current head node
head = newest // Set newly added node as the head
size = size + 1 // now that a new node is added to the chain increment its size by 1
Adding a data item from the back of the list
Process addLast(e):
newest = Node(e) // create a new node to add at the last
newest.next = null // to make newly created node last node, set its next to last
tail.next = newest // set current tails next to newly crated node. So that current tails is now 1 node before last
tail = newest // set tail to newly created node so that it is officialy the last node
size = size + 1 // now that a new node is added to the chain increment its size by 1
Remove data item from the head of the list
Process removeFirst( ):
if head == null then the list is empty // This is because cant remove a node from an empty list
head = head.next // new head is set to next node. So that 2nd node is the new head
size = size − 1 // New lists has 1 item less. But the reference from old new to new new is there
one major disadvantage in linked lists is it consumes more memory. This is because of the additional part for storing the reference.
See full implementation details here : http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html
