Data Structures - Pt 2: Linked Lists

If you are new to data structures, this post is for you. I didn't have the easiest time grasping data structures, so I wanted to share the basics of what I have learned so far to help you get started. My previous post covered stacks and queues. This one will cover the basics of linked lists.

A linked list is an ordered collection of data made up of nodes.

• Each node must have 2 properties
  1. A data property which contains the data
  2. A next property which is a reference to the next node

class Node {
    constructor(data, next=null){
        this.data = data;
        this.next = next 
    }
}

• The first node is often referred to as the "head" node and the last node is often referred to as "tail" node. The tail node will not have a reference to any other node.
• The order of nodes will not change unless we explicitly change the order by inserting and/or removing nodes.
• To access nodes, you must go through the pointers. (Linked lists do not use index numbers the same way arrays do.) Below is an example of accessing a specific node in a linked list if given an index.

getAt(index){
  let count = 0
  let node = this.head
    while(node){
      if(count === index){
      return node
      }
      count++
      node = node.next
    }
   return null
}

In addition to the basic singly linked list, there are 2 additional types of linked lists.

1. Doubly linked list
   • A doubly linked list will have both next and previous properties.
2. Circular linked list
   • A circular linked list doesn't have a tail node. Instead the last node will point to a node at an earlier point in the list, creating an infinite loop.