Singly Linked List - Data structure

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