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:
https://gist.github.com/tamg/dde1afcd8b2bd2c716b85b2f215ef58d
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:
https://gist.github.com/tamg/098c22b3bffc417eb7ee3eddb1663d3e
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.