Linked- List data structure

Previously we introduced array structures by illustrating data structures in js – Array Structures.

In this article, we will introduce the linked list structure 👇

When I finished writing the title of this article, I knew it would not be short. Original code calligraphy and painting are not easy, but also please like to encourage. 🤭

What is a linked-list?

Linked list is a common basic data structure in computer science. It is a linear list but does not store data in a linear order. Instead, it stores Pointers to the next node in each node

According to the definition of linked lists given by Wikipedia, linked lists satisfy:

A linked list is a linear list that stores a finite number of elements in an ordered fashion
Each node in the linked list stores a pointer to the next node

Several new knowledge points introduced here, linear list, sequential storage, chain storage. We need an introduction

What is a linear list

Linear tables are the most basic, simplest, and most commonly used data structures. A linear list is a type of data structure. A linear list is a finite sequence of n data elements having the same properties.

The relationship between data elements in a linear table is one-to-one, that is, all data elements are end to end except the first and last data elements (note that this applies only to most linear tables, not all. For example, a circular linked list is also a linear list at the logical level (the storage level is chained, but the last data element’s tail pointer points to the first node). Quotes from Baidu Baike

Through the above definition, we can reach the conclusion that:

The elements in a linear list are in order (note: the order does not mean ordering, but that the relative position of each element is fixed, just like when multiple knots are tied on a line, the position of each knot is in linear order by definition).

Arrays and linked lists are very classic linear lists

Sequential storage/chain storage

There are two storage modes for linear tables, namely sequential storage and chain storage

Sequential storage of linear tables uses a contiguous memory space for storage. The most common implementation is [array] (juejin.cn/post/700361…). . If you don’t know, see another article of mine that illustrates data structures: JS – Array structures

Chain storage is to store linear lists in the form of linked lists. The nodes are not contiguous in memory, but random. A pointer points to the address of the next node to ensure the sequential order between nodes. If you don’t know, don’t worry, this article is about it.

Static/dynamic linked lists

Linked lists can be divided into static linked lists and dynamic linked lists according to their storage mode. The static linked list uses sequential storage, and the dynamic linked list uses chain storage

Generally speaking, linked lists refer to dynamic linked lists

Precursor node/successor node

Precursor node: indicates the previous node. Successor node: indicates the next node

Dynamic singly linked lists

Dynamic lists are dynamically allocated memory, so there is no limit on the length of the list. The physical address of each node is not contiguous because the memory of the dynamic list is dynamically allocated. Therefore, the physical address of each node is accessed sequentially through Pointers.

The elements in a dynamic list are called nodes, and each Node contains a data field and a pointer field, data and next

Data stores the data of the current node, and next stores a reference to the next node of the current node

N nodes are linked to form a linked list, which is the chain storage structure of a linear list. Because each node of the list contains a pointer field, it is called a dynamic singly linked list. The structure is shown below.

Head node/tail node

Header pointer: The header pointer refers to the pointer to the first node that the linked list points to. If the linked list has a header, it is the pointer to the header node. The header pointer must have the function of identification, so the header pointer is usually preceded by the name of the linked list

Head: Used for permission and convenience of operation. Placed before the head of the first element, the data field usually has no real meaning

Real header: Its first node is used to store data

Virtual header: Its first node is not allowed to store data

Rear: Similar to the head pointer, but a pointer to the last node in a linked list

Code implementation

First, define the structure of Node

class Node{
    data; / / data domain
    next = null; / / pointer field

    constructor(data) {
        this.data = data
    }
}

class LinkedLint{
    head = null;
    rear = null;
    size = 0;
    
    constructor() {
        // Create a virtual head node
        let node = new Node("head")
        this.head = node
        this.rear = node
    }
}
Copy the code

Traversing the list

The way to query the list is very simple, we just need to continuously access the next node through the next pointer until next is null.

Let’s rewrite LinkedLint’s toString method first


// Iterate over the output from the beginning node to the end of the list
LinkedLint.prototype.toString = function(){
    let head = this.head
    let str = `${head.data}`

    head = head.next
    while(head){// Determine whether the next node exists
        str += ` -- -- >${head.data}`
        head = head.next
    }
    str += ` --> NULL`

    return str
}
Copy the code

And then you test it, and it works

let linkedLint = new LinkedLint();

// Insert data (insert method, insert method, insert method)
t = linkedLint.head
t.next = new Node('a1')
t = t.next
t.next = new Node('a2')
t = t.next
t.next = new Node('a3')
t = t.next
t.next = new Node('a4')

console.log(linkedLint.toString()) // head --> a1 --> a2 --> a3 --> a4 --> NULL
Copy the code

Ever think dynamic singly linked lists are a bit like JavaScript iterators? Call next repeatedly to get the next structure.

Query list

The most common way to query the ith element in the list is to iterate from the beginning node, and when it reaches the ith element, it returns, O(n) time.

Code implementation

/** * gets the element whose index is index, with subscripts starting at 0 *@param The index subscript * /
LinkedLint.prototype.get = function (index){
    // If index exceeds the list length, null is returned
    if(index >= this.size) return null
    // Get the node with subscript 0. I is the subscript of the current head node
    let head = this.head.next, i = 0

    while (i < index){
        head = head.next
        i++
    }

    return head
}

console.log(linkedLint.get(0)) // Node { data: 'a5', next: ... }
console.log(linkedLint.get(6)) // Node { data: 'a7', next: null }
console.log(linkedLint.get(7)) // null
Copy the code

Insert-head insertion

The so-called head insertion method is to insert the node after the head node (or before the head node if it is a real head node), we use virtual head node as an example

The order of nodes in the linked list generated by the header method is the reverse of the order in which the inputs are inserted

There are three steps for head insertion

Special case: If the linked list is empty, you need to point the tail pointer to the inserted node
The node to be insertednextPoints to the head nodenext
Will the head nodenextPoint to the inserted node

The time complexity is n(1).

Insert an empty list header

Non-empty linked list header inserts

Code implementation

Add the addHead method to the LinkedLint class

/** * Insert node *@param Node Node to be inserted */
LinkedLint.prototype.addHead = function(node){
    // If there is only one node, move the tail pointer to the new node
    if( this.size === 0) this.rear = node
    // Point the inserted node next to next of the head node
    node.next = this.head.next
    // Next of the first node points to the inserted node
    this.head.next = node
    // Maintain the size field
    this.size++
        
    return true
}


let linkedLint = new LinkedLint();
console.log(linkedLint.toString()) // head --> NULL

linkedLint.addHead(new Node("a4"))
linkedLint.addHead(new Node("a3"))
linkedLint.addHead(new Node("a2"))
linkedLint.addHead(new Node("a1"))
console.log(linkedLint.toString()) // head --> a1 --> a2 --> a3 --> a4 --> NULL

linkedLint.addHead(new Node("a5"))
console.log(linkedLint.toString()) // head --> a5 --> a1 --> a2 --> a3 --> a4 --> NULL
Copy the code

Insert-tail insertion

After the nodes to be inserted are inserted into the end of the current single linked list, the order of nodes in the linked list generated by the tail interpolation method is the same as the order of input insertion

The idea is simple:

Will tail pointernextPoints to the inserted node
Let the tail pointer point to the inserted node

It’s simple, but still

Code implementation

/** * Insert node *@param Node Node to be inserted */
LinkedLint.prototype.addRear = function (node){
    // Place the next of the tail pointer to the inserted node
    this.rear.next = node
    // let the tail pointer point to the inserted node
    this.rear = node
    / / to increase the size
    this.size++
    
    return true
}

console.log(linkedLint.toString()) // head --> a5 --> a1 --> a2 --> a3 --> a4 --> NULL
linkedLint.addRear(new Node("a6"))
linkedLint.addRear(new Node("a7"))
console.log(linkedLint.toString()) // head --> a5 --> a1 --> a2 --> a3 --> a4 --> a6 --> a7 --> NULL
Copy the code

Insert – Insert in the middle

The header and tail insertion methods are commonly used to initialize linked lists, and the insertion of values at specified positions is more common than the actual application.

Ideas:

Of the newly inserted nodenextPoint to theindexNode of position
willindexPosition of the precursor nodenextPoints to the newly inserted node
Special case: ifindex 为 0orsize, respectivelyThe first interpolationorThe tail interpolationCan be

The time complexity is O(n) because we need to get the precursor node of the insertion position through GET.

The code is still simple

/** * inserts the node into the specified position *@param Node Node to be inserted *@param Index Indicates the index position to be inserted *@return {Boolean} Whether the file is successfully inserted */
LinkedLint.prototype.add = function (node, index){
    if(index < 0 || index > this.size) return false
    if(index === 0) return this.addHead(node)
    if(index === this.size) return this.addRear(node)

    // Get the precursor node at index
    let previousNode = this.get(index-1)
    // The inserted node points to the next of the precursor node.
    node.next = previousNode.next
    // The precursor node points to the newly inserted node
    previousNode.next = node
    this.size++

    return true
}

console.log(linkedLint.toString()) // head --> a5 --> a1 --> a2 --> a3 --> a4 --> a6 --> a7 --> NULL

linkedLint.add(new Node('add1'), 1)
linkedLint.add(new Node('add2'), 5)

console.log(linkedLint.toString()); // head --> a5 --> add1 --> a1 --> a2 --> a3 --> add2 --> a4 --> a6 --> a7 --> NULL
Copy the code

delete

Deleting a node is the easiest operation

Make the next of the precursor node of the deleted location point to the successor node of the deleted location.

/** * Removes an element * from the list@param index
 * @return {boolean}* /
LinkedLint.prototype.delete = function (index){
    if(index < 0 || index > this.size) return false

    let previousNode = this.get(index-1)
    previousNode.next = previousNode.next.next
    
    return true
}
Copy the code

After all these words and graphs, I can’t believe I’m introducing a linked list. Code word is not easy, but also please like encouragement.

Static singly linked lists

Static lists aren’t very common, but I’m going to pick one up. Because it will be on the exam.

A static list is a sequential storage structure similar to an array. It is contiguous in physical addresses and requires pre-allocation of address space size. So the initial length of a static list is usually fixed, and the insertion and deletion operations do not need to move elements, just modify the pointer.

When we use a fixed-position element in an array as the head node, we can use the head node as the first data node. If the position of the first data node changes, then we need to use the head node to point to the position of the first data node, so we use the real head node (the head node stores the data) for static singly linked lists.

Let’s first look at static linked lists and memory structures.

A static list uses two arrays of the same size, one (data) for data elements and one (cur) for cursors.

The standby list

The static linked list shown in the figure above is not complete enough. In a static linked list, in addition to the list composed of the data itself through the cursor, there needs to be a list connecting each free position, called the standby linked list.

The purpose of the standby list is to reclaim unused or previously used (currently unused) storage space in an array for later use. That is, there are two linked lists in the physical space that a static list uses an array to claim. One joins data and the other joins unused space in the array.

It can be found from the above figure that linked list nodes are not necessarily compact stored in the array, and there may be free array items in the middle. In order to reasonably utilize the space of the array, we need to find a free node in the array for insertion every time we insert a node. The time complexity is O(n) if the array is iterated to find free space.

So we use another linked list to store all the free space in the array. We call this list the standby list. When we need to insert a node, we just need to extract the next node of the head node of the standby list, and the time complexity is reduced to O(1).

In general, the head of the standby list is at array subscript 0 (data[0]), while the head of the data list is at array subscript 1 (data[1]).

The advantage of having a standby list in a static list is that it is clear whether there are free places in the array that can be used when new data is added to the data list. For example, if the array subscript 0 in a static list holds data, then the array is full.

However, we generally don’t insert data on data[0] and data[1], thinking that this will cause us to lose the standby list and the head node of the list

Code implementation of the above mentioned functions to do it first, then add a little bit

We define the data in our LinkedList class, and then mount all of its elements to an alternate LinkedList

You could also maintain a size field to record the length of a datapool as in the dynamic singly linked list above, but I find it too cumbersome and difficult to maintain, and I won’t continue to maintain it later.

class LinkedList{
    data;
    cur;
    constructor(length){
        // The head of the standby list and the data list will take up one space each
        length += 2
        // Initialize to build a standby linked list
        this.data = Array(length)
        this.cur = Array(length)

        // Build an alternate list head node
        this.cur[0] = 2
        // Datalink header node
        this.cur[1] = -1
        this.data[1] = "head"
        // All Spaces between 2 and length-2 are mounted to the standby list
        for(let i=2; i<length-1; ){
            this.cur[i] = ++i
        }
        // Standby list tail node
        this.cur[length-1] = -1}}Copy the code

Iterate over static singly linked lists

We then add a method to traverse the list and print its contents

The idea of traversal is very simple, we just need to get the cursor (the position of the next node) from the node we started traversal until the cursor is -1

The same is true for traversal of a linked list.

// Print alternate lists and data lists
toString(){
    return 'Standby linked list:The ${!this.data[0] && this.through(0)}\n Data linked list:The ${this.data[1] && this.through(1)}`
}

// Traverses the list from index
through(index){
    let str = `The ${this.data[index]}:${index}` // The current node

    let next = this.cur[index] // Get the index of the next node of the current node
    / / traverse
    while(next ! = = -1){
        str += ` > -- -The ${this.data[next]}:${next}`
        next = this.cur[next]
    }

    return str
}
Copy the code

Insert-head insertion

We’ve already introduced the header method above, but how to implement the header method for static singly linked lists as opposed to dynamic singly linked lists?

Ideas:

Select the first node in the standby list to store data (this is a list deletion operation)
Change the cursor of the new node to the cursor of the datalink header node (that is, the new node points to the original first data node)
Change the cursor of the head node to the subscript of the new node (making the new node the first data node)

In fact, the idea and steps in the dynamic list are consistent

Remove the first node of the standby list

So we have a free node with subscript 4, and then we copy its data field and cursor it to the same subscript as the head node

Finally we place the cursor of the head node to the index of the node we are inserting

Code:

// Remove the node from the standby list, return the corresponding index of the node in the array
getNode(){
    if(this.cur[0] = = = -1) return -1

    let next = this.cur[0]// The index of the removed node
    this.cur[0] = this.cur[next]// The head node points to the next node

    return next 
}

/ / head interpolation
addHead(data){
    let index = this.getNode()

    if(index ! = = -1) {this.data[index] = data
        Node.next = this.head. Next = this.head
        this.cur[index] = this.cur[1]
        // this. Head. Next = node
        this.cur[1] = index

        return true
    }

    return false
}
Copy the code

One test run, no problem

let linkedList = new LinkedList(5);

console.log(linkedList.toString());
/* * use of undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant head:1 */

console.log(linkedList.addHead("Ha ha ha.")); // true

console.log(linkedList.toString());
/* * use of undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant -> undefined constant
Copy the code

I’m not going to go through the other methods, but it’s the same thing as a dynamically linked list. For example, a node with subscript index. Cur [index] fetches its next index, and a data[index] fetches its data field.

When you stumble across a static list, it’s like a quiz question. They give you a memory map like the one above, tell you the memory address of the first node, and ask you to calculate the memory address of the ith element in the list. 🤭

Double linked list

As the name suggests, a double-linked list is a list that changes from a one-way chain to a two-way chain. Using this data structure, we can no longer be confined to the single linked list of one-way creation in traversal operations, greatly reducing the problems in use.

This refers to a dynamic double-linked list. A double-linked list is the same as a single-linked list, except that one more pointer stores the previous node, so the node structure diagram of a double-linked list has two pointer fields

In a singly linked list, we have a data field, which stores related data, and a pointer field, which is responsible for the “connections” between the lists. In a bidirectional list, we need two pointer fields, one for backward join (next) and one for forward join (front).

Where front points to the precursor node and next points to the successor node. The end result is a two-way linked list.

The insert

Pseudo code

e3.next = e2
e3.front = e1

e1.next = e3
e2.front = e3
Copy the code

Remove operation

The remove operation is the reverse of the insert operation

Pseudo code

e1.next = e3.next
e2.front = e3.front
Copy the code

Single loop linked list

Singly linked list can also form a singly linked list by linking the head and tail of the singly linked list, which is called singly linked list

Double-loop linked lists

A bidirectional circular list can also be formed by linking the head and tail of a bidirectional circular list, which is called a bidirectional circular list.

Advantages and disadvantages of sequential and linked lists

The order sheet

Advantages:

High space utilization, data storage is continuous, high hit ratio
Access speed efficient, direct access by subscript.

Disadvantages:

Insert and delete are slow. When inserting or deleting an element, you need to traverse the data before and after the movement of the sequence table
Sufficient space needs to be allocated in advance. If the estimation is too large, a large amount of space behind the sequential table will be left idle. But overestimation can cause overflows.

Time complexity: Search operation is O(1), insert and delete operation is O(n).

The list

Advantages:

Insert and delete fast, retain the original physical order, when insert or delete an element, just need to change the pointer pointer.
There is no space limit, there is no upper limit to the storage elements, only the size of the memory space.
Dynamically allocate memory space without having to open up memory beforehand
This improves memory utilization

Disadvantages:

Take up extra space to store Pointers, more waste space, discontinuous storage, open up more space debris
Lookups are slow because you need to loop through the list as you look up.

Time complexity: The search operation is O(n) and the insert and delete operation is O(1).

conclusion

Maybe because the writing time is too long (write a whole day), the picture behind the drawing is relatively sloppy, but the code word is not easy, give the child ** a thumbs up ~~~**🤭

What is a linked-list?

Dynamic singly linked lists

Traversing the list

Query list

Insert-head insertion

Insert-tail insertion

Insert – Insert in the middle

delete

Static singly linked lists

The standby list

Iterate over static singly linked lists

Insert-head insertion

Double linked list

Single loop linked list

Double-loop linked lists

Advantages and disadvantages of sequential and linked lists

conclusion

Related Posts

Not TS yet? Get you started with TypeScript quickly

Day 27: Understanding ECMAScript String data types

Hexo personal website optimization exploration