This is the third day of my participation in Gwen Challenge

preface

Public number to nPY front-end secrets

Add vx👉16639199716, pull you into the group ao ~❤️

Linked lists in data structures are still very important, so this time to learn about linked lists, do a summary, share to you 🤭

Disadvantages of arrays

Arrays are not always the best data structures for organizing data.

Here’s why: In many programming languages, the length of an array is fixed, so it’s very difficult to add new elements when the array is already filled with data. Adding and removing elements in an array is also cumbersome. The other elements in the array need to be shifted forward or backward to reflect that the array has just been added or removed.

The list

A common basic data structure, also a linear table, does not store data in the order of a linear table. Instead, it stores Pointers on each node to the next node. That is, a linked list is a collection of nodes with discontinuous element storage, and each node uses a reference to an object to point to its successor.

Linked lists can be O(1) inserted, much faster than sequential lists, another linear list, but it takes O(n) time to find a node or access a node with a specific number, whereas sequential lists are O(log n) and O(1) respectively.

The advantages and disadvantages:

  • The linked list structure can overcome the disadvantage that arrays need to know the data size in advance. The linked list structure can make full use of computer memory space and realize flexible memory dynamic management.
  • Linked lists lose the advantage of random array reading, and because of the increased pointer field of nodes, the space overhead of linked lists is high.

Tips: 👇

“If you find that arrays are slow to use in practice, consider using linked lists instead. Linked lists can be used in almost any situation where one-dimensional data can be used, except for random access to data. Arrays are still the best choice for anyone who wants random access.”

Design an object-based linked list

The linked list we designed consists of two classes. The Node class represents nodes, and the LinkedList class provides methods for inserting nodes, removing points, displaying list elements, and other helper methods.

The Node class

The Node class contains two attributes: Element holds data on the Node, and next holds links to the next Node. We create the node using a constructor that sets the values of these two properties:

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

LinkedList class

The LinkedList class provides operations on linked lists.

// Single list insert, delete, search
        function LinkedList() {
            this.head = new Node(val)
            this.findByVal= findByVal
            this.insert = insert
            this.remove = remove
            this.diaplay = display
        }
   
            // return -1 if val is not found
            findByVal(val) {
                let current = this.head
                while(current ! = =null&& current.element ! == val) { current = current.next }return current ? current : -1
            }

            // Insert the node after the value val
            insert(newElement, val) {
                let current = this.findByVal(val)
                if (current === -1) return false
                let newNode = new Node(newElement)
                newElement.next = current.next
                current.next = newElement
            }

            // Get the previous node of nodeVal, -1 if not found, val
            // Applies to linked lists with no duplicate nodes
            findNodePreByVal(nodeVal) {
                let current = this.head;
                while(current.next ! = =null&& current.next.element ! == nodeVal) current = current.nextreturncurrent ! = =null ? current : -1
            }

            // Find the current node by index
            // Can be used to compare lists with duplicate nodes

            findByIndex(index) {
                let current = this.head,
                    pos = 1
                while(current.next ! = =null&& pos ! == index) { current = current.next pos++ }return (current && pos === index) ? current : -1
            }

            // Delete a node. If the deletion fails, return false
            remove(nodeVal) {
                if(nodeVal === 'head') return false
                let needRemoveNode = this.findByVal(nodeVal)
                if (needRemoveNode === -1) return false
                let preveNode = this.findNodePreByVal(nodeVal)
                
                preveNode.next = needRemoveNode.next
            }

            // Iterate over the node

            disPlay() {
                let res = new Array(a)let current = this.head
                while(current ! = =null) {
                    res.push(current.val)
                    current = current.next
                }
                return res
            }

            // Insert a new node at the end of the list
            push(nodeVal) {
                let current = this.head
                let node = new Node(nodeVal)
                while(current.next ! = =null) {
                    current = current.next
                    current.next = node
                }
            }
            // Insert in the header
            frontPush(nodeVal) {
                let newNode = new Node(nodeVal)
                this.insert(nodeVal,'head')}}Copy the code

[LeetCode206, Reverse linked list]

Reverse a single linked list.

Link: [leetcode] inverts a linked list

Example:

Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL

Output: 5 – > 4 – > 2 – > 3 – > 1 – > NULL

  • Invert the two nodes, pointing next of n+1 to n
  • Reverse multiple nodes: Double pointer traverses the list, repeating the above operation
  • Train of thought
    • Two Pointers traverse the linked list one after the other
    • Reversed double pointer
var reverseList = function (head) {
    let p1 = head;
    let p2 = null;
    while(p1){
        const tmp =p1.next
        p1.next=p2;
        p2=p1;
        p1=tmp;
    }
    return p2;
};
// Time complexity O(n)
// Space complexity O(1)
Copy the code

Meat today

Today, I chose LeetCode237 and deleted the nodes in the linked list. It tastes better when two of them work together

Write a function that removes a given (non-trailing) node from a linked list. The only argument passed to the function is the node to be deleted.

  • Train of thought
    • Changes the value of the truncated point to the next node
    • Delete the next node
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next=node.next.next
};
// Time and space are O(1)
Copy the code

conclusion

On the 9th day, I chose the 206 and 237 questions to learn the related knowledge of linked lists

❤️ thank you

If you think this content is quite helpful to you: click the like to support it, so that more people can see this content (collection does not like, are playing hoagie – -) pay attention to the public account to NPY front-end secrets, we learn together and progress together. If you feel good, you can also read other articles (thanks to friends for their encouragement and support 🌹🌹🌹)

Start the LeetCode journey

Double pointer to LeetCode

Leet27. Remove elements

Front-end engineers must learn the classic sorting algorithm

LeetCode20. Brackets match

LeetCode7, integer inversion

LeetCode344, reverse string