Learn Linked List (1)

what is linked list

Linear collection of data elements (aka Node), In which linear order is not given by their physical placement in memory. Instead each element points to the next element. It is a data structure consisting of a group of nodes that together represent a sequence.

what are the advantages

• Efficient Deletion of Known Nodes / O(1)
• Efficient Insertion / O(1)
• Dynamic Size
• Linked lists do not require contiguous memory allocation like Array

what are the disadvantages

• Sequential Access / O(n)
• Memory Overhead, as each node in a linked list requires additional memory for the pointer/reference to the next node.

when to use

• Implementing a Queue or Stack / O(1)
• Undo Mechanisms
• Frequent Insertions/Deletions in Middle/ O(1)

Example

structure of a single node :

class LinkedListNode {
    constructor(value, next = null){
        this.value = value;
        this.next = next
    }
}

Figure 1: This is an example of a node.

structure of linked list :

class LinkedList {
    constructor () {
        this.head = null;
        this.tail = null;
    }
}

Figure 2: This is an example of a nodelist.

Figure 3: This is an example of visual representation of Node List.

Basic Operation

Append

PseudoCode

Append(value)
    pre : value is the value to add in the list
    post : value has beed added at the tail of the list

newNode ⟵ node(value)

if(head = Ø) :
    head ← newNode
    tail ← newNode
else
    tail.next ← newNode
    tail ← newNode

end Append

Figure 4: This is an example of a nodelist append pseudocode.

Javascript Implementaion

append (value) {
        let lastNode = new LinkedListNode(value)

        if(!this.head){
            this.head = lastNode;
            this.tail = lastNode;
            return this;
        }else{
          //here this.tail is the previous last node
            this.tail.next = lastNode; //add the current lastNode reference to the previous last node next property
            this.tail = lastNode;   // change the reference of the tail to the current lastNode.
            return this;
        }
    }

Figure 5: This is an example of a nodelist append method implementation.

Visual Example

Figure 6: This is an example of visual representation of Node List Appending.

Prepend

PseudoCode

  Prepend(value)
  pre : value is the value to add in the list.
  post : value added as the head of the list

  newNode ← node(value)
  newNode.next ← head

  head ← newNode
  if(tail = Ø)
    tail ← newNode

end Prepend

Figure 7: This is an example of a nodelist prepend pseudocode.

  prepend(value){
    //create a node whose next property point to the previous head
    const newHead = node(value, this.head)  
    this.head = newHead 
    if(!this.tail){
      this.tail = newHead
    }
  }

Figure 8: This is an example of a nodelist prepend method implementation.

Figure 9: This is an example of visual representation of Node List Prepending.