Linked List - Basics

#javascript #algorithms

Linked List Brief Intro:

Linear collection data structure
Chain of nodes ⛓ - "each node contains a value and a pointer to the next node in the chain."

Singly Linked List (one direction only)

1 -> 2 -> 3 -> 4 -> null (when the pointer gets to null, it has reached the end of the linked list) 
^
Head: beginning of the linked list

//Linked List Node Class Declaration
class ListNode { 
   constructor(value = 0, next = null) { 
      this.value = value; 
      this.next = next; 
   }
}

In this Linked List series, I will be using curr (stands for current) as the main pointer to move through a Linked List.

//Using curr allows us to remember the head to return it at the end of the function

let curr = head;

1 -> 2 -> 3 -> 4 -> null
^
curr

curr = ListNode { 
          value: 1, 
           next: ListNode { 
                   value: 2, 
                    next: ListNode { 
                             value: 3, 
                              next: ListNode {
                                     value: 4, 
                                      next: null
                                   }
                          }
                 }
       }
curr.value = 1

1 -> 2 -> 3 -> 4 -> null
^ ->
curr.next (the next node based on the current node) 

curr.next = ListNode{2, ListNode{3, ListNode{4}}}
curr.next.value = 2

How to move to the next node in a Linked List?

//assigning curr to the next node 
curr = curr.next;

Here is an example:

while(curr) { //keep iterating as long as curr is not null
   curr = curr.next; 
}

While 'curr' is not null: 

1 -> 2 -> 3 -> 4 -> null
^ ->
curr.value = 1
curr.next.value = 2

curr = curr.next;

__

While 'curr' is not null: 

1 -> 2 -> 3 -> 4 -> null
     ^ ->
curr.value = 2
curr.next.value = 3

curr = curr.next;

__

While 'curr' is not null: 

1 -> 2 -> 3 -> 4 -> null
          ^ ->
curr.value = 3
curr.next.value = 4

curr = curr.next;

__

While 'curr' is not null: 

1 -> 2 -> 3 -> 4 -> null
               ^ ->
curr.value = 4
curr.next = null

curr = curr.next; 

__

1 -> 2 -> 3 -> 4 -> null
                     ^ ->
'curr' is null, stop the iteration. 
The pointer has now moved through the entire Linked List.

References & Additional Resources: