The simplest data structure and algorithm (three) linked list

Linked list – One-way linked list?

Unidirectional linked list structure diagram:

As can be seen from the structured diagram, a single necklace table uses a set of arbitrary memory space to store data elements, starting with the head pointer, its pointer to the next node, and the last pointer to null. In this case, each node has data itself and a pointer to the next node

After analyzing the structure, let’s use JS code to achieve it

1: initializes a node information, which is used to generate each node

// Initialize the node information
// 1: the pointer is null
// 2: data points to stored data
class Node {
    constructor(key){
        this.next = null;
        this.key = key; }}Copy the code

2: initializes the one-way linked list

class List {
    constructor(){
        this.head = new Node('head'); }}Copy the code

We use constructors to implement our list. I have directly generated the head node of the list to facilitate insertion and deletion later

3: Insert a new node

We know that each node in the list has a pointer to the next node, so what if we want to insert a new node? In fact, we just need to change the pointer point, we will insert the node pointer to the current node pointer, and the current node pointer to the node we need to insert

We first need a lookup function that says, where do we want to insert the node

// Find the node
    find(item){
        let currentNode = this.head;
        while(currentNode.key! ==item) {if(currentNode.next === null) {return 'Not found'
            }
            currentNode = currentNode.next;
        }
        return currentNode
    }
Copy the code

Insert node implementation

// Insert a new node after an element
    insert(newKey,item){
        / / the new element
        let newNode = new Node(newKey);
        let current = this.find(item);
        // Change the pointer pointer
        if(current === 'Not found') {return
        }
        newNode.next=current.next;
        current.next=newNode;
    }
Copy the code

Remove nodes

Remove nodes as well as insert node, we only need to change node Pointers point to the new node, but because of remove when we need to change the parent node pointer to the pointer to the current node, all we need to first check to delete a node’s parent, so how to realize, actually very simple, We just need to know that the property of the node that the pointer to the node points to is equal to the value we are looking for, and in this case the node is the parent node we want

Find the parent node

    // find Key equality
    findUpNode(newKey){
        let currentNode = this.head;
        while(currentNode.next! = =null&& currentNode.next.key! ==newKey) { currentNode = currentNode.next }return currentNode
    }
Copy the code

Deleting a node

    // To delete a node, you change the direction of next, pointing the current node next to the next node next next
    deleteNode(newKey){
        let upNode = this.findUpNode(newKey);
        if(upNode.next! = =null){
            upNode.next = upNode.next.next
        }
    }
Copy the code

OK!!!!!! Here we have the full functionality of a one-way list. I have added a view method to view the elements in our list. The complete code is attached below

class Node {
    constructor(key){
        this.next = null;
        this.key = key; }}class List {
    constructor(){
        this.head = new Node('head');
    }
    // Find the node
    find(item){
        let currentNode = this.head;
        while(currentNode.key! ==item) {if(currentNode.next === null) {return 'Not found'
            }
            currentNode = currentNode.next;
        }
        return currentNode
    }
    // Insert a new node after an element
    insert(newKey,item){
        let newNode = new Node(newKey);
        let current = this.find(item);
        if(current === 'Not found') {return
        }
        newNode.next=current.next;
        current.next=newNode;
    }
    // Find the previous node of a node
    findUpNode(newKey){
        let currentNode = this.head;
        while(currentNode.next! = =null&& currentNode.next.key! ==newKey) { currentNode = currentNode.next }return currentNode
    }
    // Delete a node
    deleteNode(newKey){
        let upNode = this.findUpNode(newKey);
        if(upNode.next! = =null){
            upNode.next = upNode.next.next
        }
    }
    // View the current list and print out each node
    view(){
        let currentNode = this.head;
        while(currentNode.next! = =null  ) {
            console.log(currentNode.next.key)
            currentNode=currentNode.next
        }
    }
}

let list = new List();
list.insert('Joe'.'head')
list.insert('bill'.'Joe')
list.findUpNode('bill')
list.deleteNode('bill')
console.log(list.findUpNode('bill'))
console.log(list.view())
Copy the code

Linked lists – Two – way linked lists

The prev pointer points to the previous node, and the prev pointer points to NULL for the head node and the next pointer points to NULL for the tail node. Let’s implement a bidirectional list!

Ps: Prev and next are both Pointers

Initializing a node information is used to generate each node

class Node {
    constructor(key){
        this.prev = null;
        this.key = key;
        this.next = null; }}Copy the code

Ps: We initialize one more pointer to a prev than to a unidirectional list

Initialize a bidirectional linked list

class List {
    constructor(){
        this.head = new Node('head'); }}Copy the code

Still declare a new head node directly

Insert a new node

The principle of insertion is the same as that of a one-way linked list and we won’t talk about it anymore

// Find the node
    find(item){
        let currentNode = this.head;
        while(currentNode.key! ==item) {if(currentNode.next === null) {return 'Not found'
            }
            currentNode = currentNode.next;
        }
        return currentNode
    }
    // Insert the node
    insert(newKey,item){
        / / the new element
        let newNode = new Node(newKey);
        let currentNode = this.find(item);
        Next of the new node points to next of the current node and next of the current node points to the new node
        if(currentNode === 'Not found') {return 'Insert node cannot be found'
        }
        if(currentNode.next! = =null){
            newNode.next = currentNode.next;
            newNode.prev = currentNode;
            newNode.next.prev = newNode;
            currentNode.next = newNode;
        }else{
            newNode.next = null; newNode.prev = currentNode; currentNode.next = newNode; }}Copy the code

Note that the insertion of the bidirectional list needs to determine whether it is the last node, and we need to change the pointer of the node’s prev and next Pointers

Remove nodes

Delete node is simpler than singly linked list, we don’t need to look up the parent node, go directly to change the prev pointer pointing to, but we need to figure out whether delete node and end node for the corresponding operation, just change node Pointers point to, pay special attention to, we need to delete the node pointer to null, Otherwise, the bidirectional list would be messed up

deleteNode(item){
    let currentNode = this.find(item)
    if(currentNode === 'Not found') {return 'Node to be deleted does not exist'
    }
    // We need to check whether the node is a head and tail node
    if(currentNode.next! = =null&& currentNode.prev! = =null) {// Neither head nor tail node
        currentNode.prev.next = currentNode.next;
        currentNode.next.prev = currentNode.prev;
        currentNode.next = null;
        currentNode.prev = null; 
    } else if(currentNode.next === null) {/ / end nodes
        currentNode.prev.next = null;
        currentNode.prev = null;
    } else if(currentNode.prev === null) {/ / head node
        currentNode.next.prev = null;
        currentNode.next = null; }}Copy the code

Here is the complete code for the bidirectional list, still adding a view function to view our list

// Initialize the node information
// 1: the pointer is null
// 2: data points to stored data
class Node {
    constructor(key){
        this.prev = null;
        this.key = key;
        this.next = null; }}// Initializes the bidirectional linked list
class List {
    constructor(){
        this.head = new Node('head');
    }
    // Find the node
    find(item){
        let currentNode = this.head;
        while(currentNode.key! ==item) {if(currentNode.next === null) {return 'Not found'
            }
            currentNode = currentNode.next;
        }
        return currentNode
    }
    // Insert the node
    insert(newKey,item){
        / / the new element
        let newNode = new Node(newKey);
        let currentNode = this.find(item);
        Next of the new node points to next of the current node and next of the current node points to the new node
        if(currentNode === 'Not found') {return 'Insert node cannot be found'
        }
        if(currentNode.next! = =null){
            newNode.next = currentNode.next;
            newNode.prev = currentNode;
            newNode.next.prev = newNode;
            currentNode.next = newNode;
        }else{
            newNode.next = null; newNode.prev = currentNode; currentNode.next = newNode; }}// Delete a node, which is easier than a single necklace table because you don't need to look up the previous node to change the prev pointer
    deleteNode(item){
        let currentNode = this.find(item)
        if(currentNode === 'Not found') {return 'Node to be deleted does not exist'
        }
        // We need to check whether the node is a head and tail node
        if(currentNode.next! = =null&& currentNode.prev! = =null) {// Neither head nor tail node
            currentNode.prev.next = currentNode.next;
            currentNode.next.prev = currentNode.prev;
            currentNode.next = null;
            currentNode.prev = null; 
        } else if(currentNode.next === null) {/ / end nodes
            currentNode.prev.next = null;
            currentNode.prev = null;
        } else if(currentNode.prev === null) {/ / head node
            currentNode.next.prev = null;
            currentNode.next = null; }}/ / check
    view(){
        let currentNode = this.head;        
        while(currentNode.next ! = =null) {
            console.log(currentNode.next.key)
            currentNode=currentNode.next
        }        
    }
}
let list = new List();
list.insert('Joe'.'head')
list.insert('bill'.'Joe')
list.insert('Cathy'.'bill')
list.deleteNode('bill')
console.log(list.view())
Copy the code

OK, by learning from the two list if we fully mastered the knowledge of the list, may be used less than in our development, but not hinder us to explore, after all, you may be asked when the interview, how to determine a linked list is two-way linked list, or how to judge the list is circular linked list (i.e., the list is end to end), OK, Leave a little tail for you to explore!

😄😄😄 don’t forget to like 😄😄😄