loading...

Data Structures - Pt 2: Linked Lists

brittjavs profile image Brittany Javalera ・2 min read

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.
Alt Text

  • 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.

Posted on by:

brittjavs profile

Brittany Javalera

@brittjavs

Software Engineer(Ruby , Javascript) Dog mom & outdoor enthusiast. Always learning and always willing to share knowledge

Discussion

markdown guide