Close

May 26, 2017

Linked Lists: Data Structures & Algorithms in JavaScript P.4

I’m learning about data structures and algorithms in JavaScript. I’m using various online resources and going to be sharing my notes as a series of blog posts. The topics are below:
  • Data Structures: List ADT | Stacks | Queues | Linked Lists | Trees, Tries & Graphs | Heaps | Hash Tables
  • Algorithms: Breadth-First Search | Depth-First Search | Binary Search | Merge Sort | Quick Sort
  • Concepts: Memory (Stack vs. Heap) | Recursion | Big O Time & Space

4. Linked List

  • A Linked List is a collection of Nodes, where each node is linked to the next or previous node using an object reference.
  • While Arrays use the index of an element as the reference to position, Linked list elements are referenced by their link/relationship to other elements in the list.
  • Head, denotes the beginning of the linked list, while tail denotes the end of the list.
  • The add method adds a new node to the list, while remove deletes a node and find returns a node from the list.
  • The Linked list utilizes two classes for its implementation: the Node class and Linked List class itself.

I. Singly Linked List:

  • A singly linked list is a type of linked list where each node only references the next node after it.
  • The implementation has an add, remove, find and print methods.
  • Here is an implementation of a Singly Linked List:

II. Doubly Linked List:

  • A doubly linked list is a type of linked list where each node references the next node after it (like singly linked list) and also the previous node before it.
  • The implementation has an add, remove, find and print methods.
  • Here is an implementation of a Doubly Linked List:

III. Circularly Linked List:

  • A circularly linked list is just like singly linked list except the last node’s next property links back to head. (tail circularly links back to head).
  • This means whenever we create a new node we set it’s next property to be this.head instead of null  like in a singly linked list.
  • One use of circularly linked list is so that we have the ability to go backward through the list without actually having to implement a doubly linked list.