Data Structures & Algorithm Linked List Day 1

Day 1

Basic data structures

We won't just learn about linked lists in the traditional way; we will also explore what the Node and LinkedList classes are, as well as all the operations that can be performed on them.

What is a Linked List?

A linked list is a collection of elements called nodes, where each node contains a data element and a reference (or link) to the next node in the sequence.
A linked list is a linear data structure in which elements are stored in nodes. Each node contains two parts:
Unlike arrays, *linked lists don’t store elements in contiguous memory locations.
* Instead, each node points to the next node, allowing dynamic memory usage and easy insertion or deletion of elements.

key point of Linked List

1. Node Structure: Linked lists consist of nodes, each containing a value and a reference to the next node. Exploring the structure and properties of nodes helps in understanding how linked lists organize and store data.
2. Head and Tail: The first node in a linked list is called the head, while the last node is referred to as the tail. Understanding the characteristics and functionality of the head and tail nodes is crucial for efficient traversal and manipulation of linked lists.

Key Characteristics:

Dynamic size: It can grow or shrink as needed.
Sequential access: Accessing elements requires traversing from the first node (head).

Types of Linked Lists:

There are three basic forms of linked lists
1. Singly linked lists.
2. Doubly linked lists.
3. Circular linked lists.

In This article, We will explore Singly-linked lists.

Singly linked lists.

Each node has a reference to the next node.

• Each node contains:
  • Data (the value you want to store).
  • A next pointer, which points to the next node in the sequence.
• The last node’s next pointer is null because there’s no node after it.

Real-Life Analogy: Arrow – Once an arrow is shot, it can only travel forward.
Once the arrow is released, it flies in a straight line without the ability to return.
Similarly, in Singly Linked List, once you move from one node to the next, you cannot go back—you can only continue moving forward.

[Data | Next] -> [Data | Next] -> [Data | Next] -> null

Operations on Singly Linked List

• Insertion:
  • Insert at the beginning
  • Insert at the end
  • Insert at a specific position
• Deletion:
  • Delete from the beginning
  • Delete from the end
  • Delete a specific node
• Traversal
• Searching
• Length

Insertion:

Insert at the beginning

Let's create a Node class

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

Let’s break down the Node class.

**The Node class represents each individual element in a linked list. Each node contains two properties:

Properties:

- Data: This holds the value stored in the node (such as a number, string, or object).
- Next: This holds a reference (or pointer) to the next node in the linked list. Initially, it's set to null because when a node is created, it's not yet linked to any other node.

Breakdown:

Constructor (constructor(data)):
This is a special method in JavaScript classes that is called when a new instance of the Node class is created.
The data parameter is passed in when creating a new node, and it stores the actual value of the node.
this.next = null; sets the next property to null initially because when a node is created, it's not connected to any other node yet.

Example:

let node1 = new Node(10); // Create a node with the value 10
console.log(node1.data);  // Output: 10
console.log(node1.next);  // Output: null (because it's not linked to any other node yet)

Let's create a SinglyLinkList class

class SinglyLinkedList {
  constructor() {
    this.head = null; // Initially, the list is empty, so the head is null.
    this.size = 0; // The size is initially 0, as there are no nodes in the list.
  }

  // Insert at the beginning
  insertAtBeginning(data) {
    let newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // The new node's next points to the current head
    this.head = newNode; // Update the head to be the new node
    this.size++; // Increment the size of the list
  }
}

The SinglyLinkedList class represents the entire linked list structure. It manages multiple Node objects and provides methods for working with the list, such as inserting, deleting, and traversing nodes and so on.

Properties:

- Head: This is a reference to the first node (or the "head") of the linked list. Initially, it is set to null, meaning the list is empty.
- Size: This keeps track of how many nodes are currently in the linked list. Initially, it’s set to 0 since the list is empty.

Breakdown:

Constructor (constructor()):

this.head = null;: This initializes the linked list with no elements, so the head points to null.
this.size = 0;: The size starts as 0 because there are no nodes in the list.

insertAtBeginning(data): for the sake of simplicity, later on, we will Deep Dive into the insertAtBeginning(data) method
let newNode = new Node(data);: This creates a new node with the value passed in as data.
newNode.next = this.head;: This links the new node to the current head (which could be nullif the list is empty or point to an existing node if the list has elements).
this.head = newNode;: This updates the head of the list to point to the new node, making it the first node in the list.
this.size++;: The size of the linked list is increased by 1 as a new node has been added.

let's Test

let list = new SinglyLinkedList();
list.insertAtBeginning(10); // List becomes: 10
list.insertAtBeginning(20); // List becomes: 20 -> 10
console.log(list.head.data); // Output: 20 (since the head is now the first node with value 20)
console.log(list.size);      // Output: 2 (since there are two nodes in the list)

Linked List deep dive Line by Line.

let's jump into the insertAtBeginning(data) method .

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

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

  // Insert a new node at the beginning of the list
  insertAtBeginning(data) {
   given data
    let newNode = new Node(data);


    newNode.next = this.head;


    this.head = newNode;


    this.size++;
  }
}

// Example Usage:
let list = new SinglyLinkedList();
list.insertAtBeginning(10); 
list.insertAtBeginning(20); 

console.log(list);

output example:

SinglyLinkedList {
  head: Node { data: 20, next: Node { data: 10, next: null } },
  size: 2
}

What Each Step Does

Node Class:

• this.data: Stores the data for the node.

• this.next: Points to the next node in the list (initialized to null because the node is alone at first).

SinglyLinkedList Class:

• this.head: Keeps track of the first node in the list (the "head").

• this.size: Tracks the number of nodes in the list.

insertAtBeginning():

• A new node is created using the Node class, and it stores the data provided.

• This new node points to the current head of the list (whatever it may be, even if null).

• The new node becomes the head of the list, taking the top position.

• The size of the list is increased by 1 each time a new node is added.

What Happens During Execution

When you insert 10:

• A new node is created with data: 10 and next: null (since it's the first node).

• This new node becomes the head of the list.

• The size becomes 1.

When you insert 20:

• A new node is created with data: 20 and next pointing to the previous node (which has data: 10).

• This new node becomes the head of the list, pushing the 10 node down.

• The size becomes 2.

Output

The final structure of the list will be:

• The head points to the node with data 20, which points to the node with data 10. The node with 10 has next: null, marking the end of the list.

• The list size is 2.

Insert at the end

Let's talk about Insert at the end

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

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

}

  // Insert at the end
  insertAtEnd(data) {
    let newNode = new Node(data);
    if (this.head == null) {
      this.head = newNode; 
    } else {
      let current = this.head;
      while (current.next != null) {
        current = current.next; 
      }
      current.next = newNode; 
    }
    this.size++;
  }

 }
// Example Usage:
let list = new SinglyLinkedList();
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
console.log(list);

output example

SinglyLinkedList {
  head: Node { data: 10, next: Node { data: 20, next: Node { data: 30, next: null } } },
  size: 3
}

insertAtEnd() Method Explanation

• A new node is created using the Nodeclass. This node will store the data provided and its nextpointer will initially be null(since it will be the last node in the list)

• If the list is empty (head is null), the new node is set as the head of the list. This means the list will only have one node, and this new node will be the first (and only) element in the list.

• If the list is not empty, we need to traverse the list to find the last node (the node whose nextis null). We start from the head and move from one node to the next until we reach the last node.

• Once we find the last node, we set its nextpointer to the newly created node. This effectively adds the new node to the end of the list.

• The size of the list is increased by 1 each time a new node is added at the end.

What Happens During Execution

When You Insert 10 (First Insertion):

• A new node is created with data: 10 and next: null (since it’s the only node and hence the last).

• Since the list is empty (head is null), this new node becomes the head of the list.

• The list size becomes 1.

When You Insert 20 (Second Insertion):

• A new node is created with data: 20 and next: null (it will be the new last node).

• The list is not empty, so we traverse the list starting from the head to find the last node (which currently holds the data 10).

• The next pointer of the last node (node with data: 10) is updated to point to the new node with data: 20.

• The list size becomes 2.

When You Insert 30 (Third Insertion):

• A new node is created with data: 30 and next: null.

• We traverse the list to find the current last node, which is the node with data: 20.

• The nextpointer of the last node (node with data: 20) is updated to point to the new node with data: 30.

• The list size becomes 3.

Final Structure of the List

After inserting 10, 20, and 30:

• The head points to the node with data: 10.

• The node with data: 10 points to the node with data: 20.

• The node with data: 20 points to the node with data: 30.

• The node with data: 30 has next: null, marking it as the last node in the list.
  This forms the linked list: 10 -> 20 -> 30 -> null.

Output

The final structure of the list will be:

The head points to the node with data: 10.
The node with data: 10 points to the node with data: 20, and the node with data: 20 points to the node with data: 30.
The node with data: 30 has next: null, indicating the end of the list.
The list size is 3.

Insert at a specific position

Let's talk about Insert at a specific position

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


class SinglyLinkedList {

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

  }
  // Insert at the beginning
  //insertAtBeginning... method 

  // Insert at the end
  //insertAtEnd... method

  // Insert at a specific index
  insertAtIndex(data, index) {
    if (index < 0 || index > this.size) {
      return console.log('Invalid index');
    }

    let newNode = new Node(data);
    if (index === 0) {
      // Insert at the head
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let current = this.head;
      let previous;
      let count = 0;

      // Traverse to the desired index
      while (count < index) {
        previous = current;
        current = current.next;
        count++;
      }
      // Insert the new node between previous and current
      previous.next = newNode;
      newNode.next = current;
    }
    this.size++;
  }

}


// Example Usage:
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);

// Insert at index
list.insertAtIndex(15,1);

insertAtIndex() Method Explanation

1. A new node is created using the Nodeclass with the given data. The nextpointer of the new node is initially set to null.

2. If no indexis passed (i.e., index === undefined), the method logs an error message: "Please provide the index to a specific position" and returns immediately. This ensures that the method doesn't proceed without a valid index, preventing unintended behavior.

3. The method checks if the given indexis valid:
   If the indexis less than 0 or greater than the current size of the list, it logs an error message ("Invalid index") and exits the method.

4. If the indexis 0, the new node is inserted at the beginning of the list:
   The nextpointer of the new node is set to the current headof the list.
   The headis updated to point to the new node, making it the first node in the list.

5. If the indexis greater than 0, the list is traversed to find the node at the desired index:
   The method starts at the headand moves through the list until it reaches the position just before the specified index.
   It keeps track of the previousnode and the currentnode during the traversal.

6. Once the correct position is reached:
   The nextpointer of the previousnode is updated to point to the new node.
   The nextpointer of the new node is set to the currentnode, placing the new node between the previousand currentnodes.

7. The size of the list is increased by 1 after the insertion.

What Happens During Execution

Let's say you have an initial list: head -> 10 -> 20 -> 30.
You want to insert the value 15 at index 1.

1. Index Validation: The method checks if index 1 is valid (which it is, because the size of the list is currently 3).

2. Node Creation: A new node is created with data: 15 and next: null.

3. Inserting at Index: Since the index is not 0, the method traverses the list to the desired position:
   Starts at the head(node with data 10).
   After one iteration, previouspoints to 10, and currentpoints to 20.

4. Insertion: The new node is inserted between the 10node and the 20node:
   The nextpointer of the previousnode (10) is updated to point to the new node (15).
   The nextpointer of the new node is updated to point to the currentnode (20).

5. Size Update: The size of the list is increased by 1.

Final Structure of the List

After inserting 15at index 1 into the list head -> 10 -> 20 -> 30:

The head points to the node with data: 10.
The node with data: 10 points to the node with data: 15.
The node with data: 15 points to the node with data: 20.
The node with data: 20 points to the node with data: 30.
The node with data: 30 has next: null, marking the end of the list.
The linked list will now look like this:
10 -> 15 -> 20 -> 30 -> null

Output

The final structure of the list will be:

The head points to the node withdata: 10.
The node with data: 10 points to the node with data: 15.
The node with data: 15 points to the node with data: 20.
The node with data: 20 points to the node with data: 30.
The node with data: 30 has next: null, indicating the end of the list.
The list size is now 4.

Deletion:

Delete from the beginning

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

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

  // Insert at the beginning
  //insertAtBeginning... method 

  // Insert at the end
  //insertAtEnd... method

  // Insert at a specific index
  //insertAtIndex... method

  // Delete the first node
  deleteFirst() {
    if (this.head == null) return null; // If list is empty
    this.head = this.head.next; // Move head to the next node
    this.size--;
  }


}

// Example Usage:
const list = new SinglyLinkedList();

// Insert at the beginning
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);

// Insert at the end
list.insertAtEnd(40);


// Delete operations
list.deleteFirst(); 

deleteFirst() Method Explanation

Purpose: The deleteFirst() method removes the first node (or "head") from the linked list. It’s a common operation in linked lists for cases where you want to delete the starting element.

Method Steps:

1. Check if the List is Empty:
   The method first checks if this.head is null, meaning the list is empty. If so, it returns nullimmediately since there's nothing to delete.

2. Move the Head Pointer:
   If the list is not empty, it updates the headpointer to point to the next node in the list (this.head.next). This effectively "removes" the first node because headnow points to the second node.

3. Decrease the Size:
   After removing the first node, the sizeproperty of the list is decreased by 1, keeping track of the updated list length.

What Happens During Execution

Let's say we have the following list initially:

head -> 10 -> 20 -> 30 -> 40 -> null
First Deletion (list.deleteFirst()):

The head is pointing to 10, which is the first node.
The deleteFirst() method checks that the list is not empty, then updates head to point to 20, the next node in the list.
The node 10 is now effectively removed from the list, and the list size decreases by 1.
Current list structure after first deletion:

head -> 20 -> 30 -> 40 -> null
Second Deletion (another list.deleteFirst()):

head is now 20, so the method updates head to 30, removing 20 from the list.
The list size decreases by another 1.
Current list structure after second deletion:

head -> 30 -> 40 -> null
Final Structure of the List
If the initial list was 10 -> 20 -> 30 -> 40 -> null, after two deleteFirst() calls, the list structure is:

head -> 30 -> 40 -> null
Output
After calling deleteFirst():

The list no longer contains the first node of the original list.
The head points to the new first node after each deletion.
The size property accurately reflects the new list length.
If any more calls to deleteFirst() are made until the list is empty, head will eventually become null.

Coming soon...