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.