linked-lists

Linked Lists

A linked List is used to represent sequential data. It is a data structure where each element is a separate object, called a node, that stores a reference (pointer)to the next node in the list.
The node represented by value and a pointer commonly referred to as next. In js, linked lists can be implemented using objects and arrays.

---

Types of Linked Lists

1. Singly Linked List :
   Each node in the list contains a reference or a pointer to the the next node in the list.
   The last node in the list (tail) contains a reference to null, indicating the end of the list.
   The main disadvantage of this, is that you can only traverse the list in one direction, from the first node(head) to the last node(tail)
2. Doubly Linked List :
   A doubly linked list is similar to a singly linked list, but in a ddition to a next reference(pointer), each node also has a prev pointer, which points to the previous node.
   This allows for easier traversal in both directions and can be useful in certain types of algorithms
3. Circular Linked Lists :
   This is a variation of a singly linked list where the last node points back to the first node(head), forming a circular loop.
   The main advantage of a circular linked list is that it allows for efficient implementation of certain algorithms such as traversing through a loop

---

Time Complexity

Access	Lookup	Insert(at)	Deletion
O(n)	O(n)	O(1)	O(n)

Access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality as compared to linked lists.

---

Basic Operations

1. Traverse :

   function traverse_list(head)
   //first node of the linked list
     current = head
     //loop to iterate through the list as long as "current" is not null
     while current != null
       //print the stored in the current node using "current.data"
       print current.data
       //move current pointer to the next node by assigning "current.next" to current and the loop continues
       current = current.next
   end function

2. Prepend :
   will add new node at the start of the list and the head of the list will now point to the new node.

   function Prepend(head, data)
   //create node and pass data parameter
     new_node = create_node(data)
     //set "next" pointer of the new node to point to the current head
     new_node.next = head
       //update head of the list to be the new node
       head = new_node
       //move current pointer to the next node by assigning "current.next" to current and the loop continues
   end function

3. Append :
   will add the new node at the end of the list, and the last node's next pointer will point to the new node

   function append(head, data)
   //create new node
       newNode = create_node(data)
       //init var current and initialize it to equal to head
       current = head
       //check if the head of the list is null, 
       if (current = null)
           //set head to equal new node
           head = newNode
       else 
          //if head does not equal to null, loop to iterate till the last node(tail)
           while current.next != null
               current = current.next
               //set next pointer of the last node to point to the new node(adding the new node to the end)
           current.next = newNode
       end if
     end function

---

Constraints

• Empty linked list (head is null)
• Single node
• Two nodes
• Linked list has cycles.

: Clarify beforehand with the interviewer whether there can be a cycle in the list. Usually the answer is no and you don't have to handle it in the code

To see how a linked list is implemented see here

---

Related Questions

No	Problem Statement
1.	Reverse Linked List

---

References

Articles

1. Medium

Videos

2. Coursera