資料結構與演算法鍊錶

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

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 SingleLinkList 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;   // Store the data value (like 10, 20, etc.)
    this.next = null;   // Initialize the next pointer as null
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;   // Initially, the list is empty, so the head is null
    this.size = 0;      // The size of the list starts at 0
  }

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

    // Explanation:
    // First time: If we insert 10, the newNode looks like this -> Node { data: 10, next: null }
    // Second time: If we insert 20, the newNode looks like this -> Node { data: 20, next: null }

    // Step 2: Point the new node's next property to the current head of the list
    newNode.next = this.head;

    // Explanation:
    // First time: Since the list is empty (this.head is null), newNode's next is set to null.
    // Second time: this.head is now the node with data 10, so newNode’s next will point to the node with data 10. 
    // So it looks like this: Node { data: 20, next: Node { data: 10, next: null } }

    // Step 3: Make the new node the new head of the list
    this.head = newNode;

    // Explanation:
    // First time: Now, the new node becomes the head. The list looks like this: Node { data: 10, next: null }.
    // Second time: The new node (with data 20) becomes the head, and it points to the previous head (which is the node with data 10).

    // Step 4: Increment the size of the list
    this.size++;

    // Explanation:
    // First time: The size is now 1 because there is one node (data 10).
    // Second time: The size becomes 2 because we added another node (data 20).
  }
}

// Example Usage:
let list = new SinglyLinkedList();
list.insertAtBeginning(10);  // First insertion: the list becomes [10]
list.insertAtBeginning(20);  // Second insertion: the list becomes [20 -> 10]

console.log(list);

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

Coming soon...

以上是資料結構與演算法鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！