Skip to content

Latest commit

 

History

History
107 lines (81 loc) · 4.51 KB

README.md

File metadata and controls

107 lines (81 loc) · 4.51 KB
Raw

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

  1. Coursera