Intro To Data Structures - Linked Lists

Linked Lists

     A linked list is a linear data structure, whose order is not given by their physical placement in memory. Instead, it consists of nodes where each node contains a data field and a pointer to the next node in the list. Which means linked lists are stored in non-contiguous blocks of memory.

Creating A Node Constructor

    The first step in creating a Linked List is to build the Node Class Constructor. The node will have two variables, the data and the pointer to the next node. Whenever the Linked List goes to make a new node, it will create an instance of the Node class.

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

Building A Linked List

    Now it's time to start building the Linked List. We are going to use a Class Constructor to create the foundation for our Linked List. The list is going to have two values, the head and the size of the list. The head is going to always indicate the first node in the list. When a list is empty your head value is going to be set to null.

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
}

Inserting Into A Linked List

   I am going to cover two methods of insertion in this post. The first and most simple method is to insert first. 

insertFirst(data) {
    // Create a New Node
    // Set the New Node to the head
    this.head = new Node(data, this.head);
    // Add one to the size
    this.size++;
}

     
    The second method for the Linked List is going to be insert last. In the best-case scenario, you will have an O(1) Time Complexity if there is no current head and the node can be inserted first. Otherwise, you will have to traverse to the end of the list in order to find the last node. Which would end up resulting in an O(n) Time Complexity.

insertLast(data) {
    // Check if there is already a head
    if (!this.head) {
        // If there is no head, insert the Node first
        this.insertFirst(data);
    } else {
        // Set a variable to the head node
        let position = this.head;
        // Create a While Loop that continues until there is no more Nodes
        while (position.next) {
            // Increment the current position to the next Node 
            position = position.next;
        }
        // Set the next pointer of the last Node to your new Node Instance
        position.next = new Node(data)
        // Increment list size by one
        this.size++;
    }
}

In the next post on Linked Lists, we will be covering the many ways of removing, finding, and even inserting more Nodes.