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

- Traversal
- Searching
- Length
- Insertion:
- Deletion:
- Delete from the beginning
- Delete from the end
- Delete a specific node

### 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 `null`

if 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

`Node`

class. This node will store the data provided and its`next`

pointer 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

`next`

is`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

`next`

pointer 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

`next`

pointer 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

- A new node is created using the
`Node`

class with the given data. The`next`

pointer of the new node is initially set to`null`

. If no

`index`

is 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.The method checks if the given

`index`

is valid:

If the`index`

is less than`0`

or greater than the current size of the list, it logs an error message ("Invalid index") and exits the method.If the

`index`

is`0`

, the new node is inserted at the beginning of the list:

The`next`

pointer of the new node is set to the current`head`

of the list.

The`head`

is updated to point to the new node, making it the first node in the list.If the

`index`

is greater than`0`

, the list is traversed to find the node at the desired index:

The method starts at the`head`

and moves through the list until it reaches the position just before the specified`index`

.

It keeps track of the`previous`

node and the`current`

node during the traversal.Once the correct position is reached:

The`next`

pointer of the`previous`

node is updated to point to the new node.

The`next`

pointer of the new node is set to the`current`

node, placing the new node between the`previous`

and`current`

nodes.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`

.

Index Validation: The method checks if index

`1`

is valid (which it is, because the size of the list is currently`3`

).Node Creation: A new node is created with

`data: 15`

and`next: null`

.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,`previous`

points to`10`

, and`current`

points to`20`

.Insertion: The new node is inserted between the

`10`

node and the`20`

node:

The`next`

pointer of the`previous`

node (`10`

) is updated to point to the new node (`15`

).

The`next`

pointer of the new node is updated to point to the`current`

node (`20`

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

#### Final Structure of the List

After inserting `15`

at 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 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`

, indicating the end of the list.

The list size is now `4`

.

## Top comments (0)