All the complete code for this series of articles on data structures and Algorithms has been uploaded to Github. If you want the complete code, you can go there directly. If you can, please click Star

Github.com/Lpyexplore/…

The previous article explained the related knowledge of linked lists and implemented a linked list structure with code. So this article will introduce another special kind of linked list structure, called bidirectional linked list. As the name implies, regular lists traverse the elements of a structure starting at the head, so a bidirectional list can traverse both from the beginning and from the end of the structure.

Explain what a linked list is and implement a linked list structure manually in code

This article will elaborate on the concept of a bidirectional linked list and how to achieve a bidirectional linked list.

Public account: Front impression

Sometimes send book activities, remember to pay attention to ~

[Interview questions], [front-end required e-book], [data structure and algorithm complete code], [front-end technology communication group]

What is a bidirectional linked list

In the last article, we used a real-life example to explain the concept of a linked list, so this article will continue this example and make some changes to explain what a two-way linked list is

Let’s look at this example:

In a classroom, all the desks are in a row, as shown in the pictureAt some point in your school life, I’m sure you’ve been asked to remember who’s sitting next to you. So in this example, the teacher asked the students to remember their front and back tables. The students sitting in the first row need to remember that they are the students in the first row and who is behind them. Students in the last row should remember who is at the front table and who is in the last row. As shown in figure:This row is equivalent to one seatBidirectional linked lists.

Suppose one day, the teacher could not remember each student’s name, so he asked: What is the name of the third person in the line? In this case, we should start counting from the first student. For example, we should start counting from the little five sitting in the first place in the picture: the first person is little five, and his back desk is little seven; So the second person is small seven, and his back table is small one; So the third guy is going to be 1 less. At this time the teacher asked small 1: what is the name of your front desk? What’s the name of your back table?

At the beginning, the teacher asked each student to remember his front desk and his back desk, so at this time, Small 1 could quickly tell the teacher that his front desk was small 7 and his back desk was small 6.

However, let’s imagine that in the example of linked list structure in the last article, if the teacher asks the name of the desk in front of little 1 after learning that the third person is little 1, can Little 1 answer? No, because the teacher only let each student remember their own back table, so now want to know the name of the front table of small 1, so the name of the third student is small 1, so his front table is in the second position, so start from the first student, the first student is small 5, his back table is small 7; So the second student is 7. Of course, the number of students in this example is a little small, but once the number is large, ask a student to count the names of their front desks from the beginning every time.

It can be seen that it is necessary for each student to remember his front desk and back desk, because in some cases, problems can be solved quickly.

With all that said, let’s take a lookTwo-way linked listWhat does it look like, as shown hereYou can see the contrastChain table structure.Two-way linked listThere’s an extra pointertailIt refers to the last element, just like the student in the example remembered that he was the last row.

Two, the method of bidirectional linked list

Because a bidirectional list is a special form of a linked list, the common methods for both are the same, but the implementation is different. Let me list some common methods, as shown in the following table

methods	meaning
append()	Appends elements to the end of a bidirectional list
insert()	Inserts an element at a location in a bidirectional linked list
get()	Gets the element at the corresponding position of the bidirectional list
indexOf()	Gets the index of an element in a bidirectional linked list
update()	Modifies the value of an element at a location in a bidirectional linked list
removeAt()	Removes an element at a location in a bidirectional list
remove()	Removes an element from a bidirectional list
isEmpty()	Check whether the bidirectional list is empty
size()	Returns the number of elements in a bidirectional list
toString()	Displays all elements of a bidirectional list as a string

Let’s use JavaScript to implement these methods

Three, use code to achieve bidirectional linked list

Create a constructor

Start by creating a large constructor to hold the properties and methods of the bidirectional list.

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0
}
Copy the code

Where, the attribute head represents the first element in the bidirectional list; The tail attribute represents the last element in the bidirectional list

(2) Create an internal constructor

Each element of a bidirectional list has three attributes, prev, item, and next, which indicate who is the element before it, the value that stores it, and who is the element after it. So we’re going to create an inner constructor inside the constructor of the bidirectional list that we’ll use to create an instance object of the element later

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null}}Copy the code

(3) Implement append() method

The append() method simply adds the element to the end of the bidirectional list.

Implementation idea:

Start by creating an instance object of the new elementnode
First check whether there are elements in the bidirectional list, if there are no elements, then attributeheadAnd attributestailAll point tonode, and finally attributelength + 1
If there is an element in the bidirectional list, there is an extra pointer in the bidirectional listtailSo we have to implementappend()The method is also a lot more convenient, just need totailPoint to thenodeAnd then put the original trailing elementold_node 的 nextPoint to thenodeAnd willnode 的 prevAttribute points toold_nodeOk, and then propertieslength + 1

To make it easier for you to understand, LET me show you a GIF:

So that’s the idea, so let’s implement this method

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Add the element at the end
    DoubleLinkedList.prototype.append = function (item) {
    	// 1. Create an instance object for the new element
        let node = new Node(item)
		
		// 2. Check whether there are elements in the bidirectional list
        if(this.length === 0) {
            this.head = node
            this.tail = node
        }
        else {
            node.prev = this.tail
            this.tail.next = node
            this.tail = node
        }
		
		// 3. Bidirectional linked list element + 1
        this.length ++
    }
}
Copy the code

Now let’s use this method

let dl = new DoubleLinkedList()

dl.append('js')
dl.append('python')
Copy the code

So the list looks like this

(4) Implement insert() method

The insert() method inserts elements at the specified index position. You pass in two arguments. The first is position, which indicates the position to insert the element. The second argument is item, which represents the value of the element

Implementation idea:

Create a new element instance objectnode
Determines the specified index locationpositionOut of bounds, that is, less than 0, or greater than the length of the bidirectional list. If out of bounds, return false
judgepositionIs it 0. If it’s 0, then we just take the first element of the bidirectional list, which isheadThe corresponding elementold_nodeAssigned tonodethenextProperty, and then thenodeAssigned toold_node 的 prevProperty, and then thenodeAssigned tohead, means that the first element of the list is nownode
ifpositionIf the value is not 0, the bidirectional linked list is traversed and the index traversed is recordedindex, traversal the last elementprevAnd in theindexThe element at the index positioncurrentwhenindex == positionWhen willnodeAssigned toprevthenextProperties, whichcurrentAssigned tonodethenextProperty, and then theprevAssigned tonode 的 prevProperty, and finally willnodeAssigned tocurrent 的 prevattribute
attributelength + 1

To make it easier for you to understand, LET me show you a GIF: After looking at the implementation of the method, let’s use the code to implement the method

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Inserts the element at the specified location
    DoubleLinkedList.prototype.insert = function (position, item) {
        // 1. Determine whether the boundary is crossed
        if(position < 0 || position > this.length) {
            return false
        }
        // 2. Create an instance object for the new element
        let node = new Node(item)
        let index = 0
        let current = this.head
        let prev = null
        
        // 3. Check whether the insertion position is equal to the number of elements
        if(position === this.length) {
        	// When position is equal to length, it is equivalent to adding elements at the end
            this.append(item)
        }

		// 4. Determine whether the element is added to the first position
        else if(position === 0) {
            node.next = this.head
            this.head.prev = node
            this.head = node
            this.length ++
        }
        else {
        	// 5. Traverse the list until you find the element in position
            while (index < position) {
                prev = current
                current = current.next
                index ++
            }
            // 6. Insert a new element
            prev.next = node
            current.prev = node
            node.prev = prev
            node.next = current
            this.length ++
        }
    }
}
Copy the code

Let’s use this method

let dl = new DoubleLinkedList()

dl.insert(0.'C++')
Copy the code

So the bidirectional list looks like thisExecute onceinsert()methods

di.append('js')              // Add element js at the end
dl.insert(1.'python')       // Insert the element python at index 1
Copy the code

So the bidirectional list looks like thisAnd then finally, we index theta to theta3Inserts elements at the position ofjavaBecause at this timelength = 3, the number of bidirectional linked list elements is3, which is equivalent to adding elements at the end

dl.insert(3.'java')
Copy the code

So the linked list looks something like this

(5) Implement get() method

The get() method just gets the element at that position. You need to pass in a parameter, position, indicating that you want to get the index of the element

Implementation idea:

judgepositionOut of bounds. If out of bounds, return false
Traverses the linked list while recording the current indexindexwhenindex == positionReturns the element at the current position

This method is pretty simple, almost like the get() method for linked lists, so let’s see

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Get the element at the corresponding position
    DoubleLinkedList.prototype.get = function (position) {
        if(position < 0 || position > this.length - 1) {
            return false
        }
        let index = 0
        let current = this.head
        while (index < position) {
            current = current.next
            index ++
        }
        return current.item
    }
}
Copy the code

Let’s use that method

let dl = new DoubleLinkedList()

dl.append('C++')
dl.append('js')
dl.append('python')

dl.get(-2)           / / returns false
dl.get(0)            / / return a c + +
dl.get(2)            / / returns a python
dl.get(3)            / / returns false
Copy the code

(6) Implement indexOf() method

The indexOf() method, like an array, returns the indexOf an element in a bidirectional list, or -1 if the element does not exist in the bidirectional list.

It’s a very simple idea, so I’m not going to go into the details, but I’m going to look at the code

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Get the index of the element
    DoubleLinkedList.prototype.indexOf = function (item) {
        let current = this.head
        let index = 0
        
        // 1. Iterate through the bidirectional list
        while (index < this.length) {
        	// 2. Find the corresponding element and return the index value
            if(current.item === item) {
                return index
            }
            else {
                index ++
                current = current.next
            }
        }
        // 3. No corresponding element is found, return -1
        return -1}}Copy the code

Let’s use that method

let dl = new DoubleLinkedList()

dl.append('C++')
dl.append('js')
dl.append('python')

dl.indexOf('C++')           / / returns 0
dl.indexOf('js')            / / returns 1
dl.indexOf('python')        / / return 2
dl.indexOf('java')          / / return 1
Copy the code

(7) Implement update()

The update() method is used to modify the value of an element at a location in a bidirectional list. So this method takes two arguments. The first argument is position, which represents the index of the element to be modified. The second parameter, NewItem, represents the modified value

The implementation of this method is exactly the same as a normal linked list, so I won’t explain the specific implementation of the idea, directly look at the code

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Modify the element at a location
    DoubleLinkedList.prototype.update = function (position, item) {
    	
    	// 1. Determine whether the boundary is crossed
        if(position < 0 || position >= this.length) {
            return false
        }
        let index = 0
        let current = this.head
        
        // 2. Iterate through the bidirectional list until the corresponding element is found
        while (index < position) {
            index ++
            current = current.next
        }
        // 3. Change the value of the element in the position index
        current.item = item
        return true}}Copy the code

Let’s use that method

let dl = new DoubleLinkedList()

dl.append('C++')
dl.append('js')
dl.append('python')
Copy the code

The linked list looks something like thisNow I’m gonna callupdate()Method to change the index position to2The value of the element

dl.update(2.'java')
Copy the code

The linked list looks something like this

Implement the removeAt() method

The removeAt() method is used to remove an element from a location in a bidirectional list. This method simply passes in a single argument, Position, indicating the index of the element that you want to remove

Implementation idea:

To determinepositionWhether it is out of bounds, if it is out of bounds, it returns directlyfalseFailed to remove the element
If the boundary is not crossed, then judgepositionWhether it is0If, is equal to the0, then directly put the first linked listnextThe value assigned toheadAnd thenlength - 1
ifpositionIs not equal to0And is equal to thelength - 1, the preceding element of the trailing element, i.etail 的 prevOf the corresponding elementnextProperty set tonullAnd willtailPoints to the currenttail 的 prevAnd the lastlength - 1
ifpositionNeither is equal to the0Phi is not equal to philength - 1, traverses the bidirectional linked list and records the current indexindex, traversing the current elementcurrent.currentThe last element ofprev
whenindex === positionWhen willcurrentThe next element of, i.ecurrent 的 nextAttribute value assigned toprev 的 nextProperty, while willcurrentOf the next element ofprev 的 prevProperty set toprevAnd the lastlength - 1

In order to give you a better understanding of the implementation of this method, I made a GIF to help you understand, as shown in the figure So with that thought out of the way, let’s go straight to the code

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Remove an element from a position
    DoubleLinkedList.prototype.removeAt = function (position) {
        // 1. Determine whether the boundary is crossed
        if(position < 0 || position >= this.length) {
            return false
        }
        
        // 2. Check whether the cleared element is unique in the list
        if(position === 0 && position === this.length - 1) {
            this.head = null
            this.tail = null
        }
        // 3. Check whether the cleared element is the first element in the list
        else if(position === 0) {
            this.head.next.prev = null
            this.head = this.head.next
        }
        // 4. Check whether the cleared element is the last element in the list
        else if(position === this.length - 1) {
            this.tail.prev.next = null
            this.tail = this.tail.prev
        }
        else {
            let current = this.head
            let prev = null
            let index = 0
            // 5. Iterate through the bidirectional list
            while (index < position) {
                index ++
                prev = current
                current = current.next
            }
            // 6. Delete the element in the corresponding position
            prev.next = current.next
            current.next.prev = prev
        }
        // 7. Number of elements - 1
        this.length --
        return true}}Copy the code

Let’s use that method

let dl = new DoubleLinkedList()

dl.append('C++')
dl.append('js')
dl.append('python')

dl.removeAt(2)         // Drop the element at index 2
Copy the code

So the bidirectional list looks like this

(9) Implement the remove() method

The remove() method removes an element from a two-way list and returns the index position of the deleted element, or false if there is no such element. This method requires passing in a parameter data to find the corresponding element in the linked list

Implementation idea:

Use the encapsulation aboveindexOf()Methods,dataPassed in as a parameterdataIndex in a linked listindex 。
Use what’s encapsulated aboveremoveAt()Methods,indexPassed as a parameter, it can be implementedremove()Method function.

Let’s just write some code to implement this method

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Remove an element
    DoubleLinkedList.prototype.remove = function (data) {
    	// 1. Obtain the index of data in the bidirectional linked list
        let index = this.indexOf(data)
		
		// 2. Use the removeAt() method to remove data from the bidirectional list
        this.removeAt(index)
        
        // 3. Returns the index of the deleted element data in the bidirectional linked list
        return index
    }
}
Copy the code

Let’s use that method

let dl = new DoubleLinkedList()

dl.append('C++')
dl.append('js')
dl.append('python')

dl.remove('js')            // Return 1, where length = 2
dl.remove('python')        // Return 1, in which case length = 1
Copy the code

The linked list looks something like this

(10) Implement isEmpty()

The isEmpty() method checks whether there are any elements in the bidirectional list. Return false if there are elements; Otherwise, return true

The implementation idea of this method is very simple, directly determine whether the attribute length is equal to 0.

So without further ado, let’s write code to implement this method

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Check whether the bidirectional list is empty
    DoubleLinkedList.prototype.isEmpty = function () {
        if(this.length === 0) {
            return true
        }
        else {
            return false}}}Copy the code

Let’s use that method

let dl = new DoubleLinkedList()

dl.isEmpty()             // Returns true if there are no elements in the bidirectional list

dl.append('C++')
dl.append('js')
dl.append('python')

dl.isEmpty()             // Return false if there are three elements in the bidirectional list
Copy the code

(11) Implement the size() method

The szie() method simply returns the number of elements in the list

So let’s implement that method

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Return the number of bidirectional linked list elements
    DoubleLinkedList.prototype.size = function () {
        return this.length
    }
}
Copy the code

Let’s use that method

let dl = new DoubleLinkedList()

dl.size()             // Returns 0, in which case there are no elements in the bidirectional list

dl.append('C++')
dl.append('js')
dl.append('python')

dl.size()             // Returns 3, where there are 3 elements in the bidirectional list
Copy the code

(12) Implement toString()

The toString() method is a string representation of all elements in a bidirectional list

The implementation idea is very simple, is to traverse each element in the bidirectional list, and each element in the form of a string can be joined

So let’s implement that method

function DoubleLinkedList() {
    / / property
    this.head = null
    this.tail = null
    this.length = 0

	// The constructor of the element
    function Node(item) {
        this.item = item
        this.next = null
        this.prev = null
    }

	// Display bidirectional linked list data
    DoubleLinkedList.prototype.toString = function () {
        let current = this.head
        let string = ' '
        while (current) {
            string += current.item + ' '
            current = current.next
        }
        return string
    }
}
Copy the code

4. Supplement of bidirectional linked list

In fact, bidirectional linked lists are usually used in more scenarios, and it is sometimes more efficient than ordinary linked list data operations.

Such as: If we have a regular list with length = 9999 and we want to delete the element with index 9997, then we can only iterate 9998 times from the first element of the list, starting with the element pointed by head, until we find the element with index 9997. This is very inefficient.

So what if you replace a regular list with a bidirectional list? When we learn to delete index as9997We can calculate first9997 与 9999-1 = 9998The difference,9997 与 0If the former difference is small, it can be from the bidirectional linked listtailThe element to which it points traverses forward; On the other hand, from theheadThe element pointing to is iterated backwards. As shown in figure

Five, the summary

This is the end of the bidirectional list, I hope you have a deeper understanding of the bidirectional list. In the next article, I’ll talk about hash tables.

Then you can pay attention to my wechat official account: Front Impressions. After this column is finished, I will put notes on each data structure and algorithm on my official account, where you can go to get them.

Or you can go to my Github to get the complete code, please click Star

Github.com/Lpyexplore/…

You’re not gonna give me a “like” when you see this?

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

【 Data structure and algorithm 】 Explain in detail what is a bidirectional linked list, and manually implement a bidirectional linked list structure with code

What is a bidirectional linked list

Two, the method of bidirectional linked list

Three, use code to achieve bidirectional linked list

Create a constructor

(2) Create an internal constructor

(3) Implement append() method

(4) Implement insert() method

(5) Implement get() method

(6) Implement indexOf() method

(7) Implement update()

Implement the removeAt() method

(9) Implement the remove() method

(10) Implement isEmpty()

(11) Implement the size() method

(12) Implement toString()

4. Supplement of bidirectional linked list

Five, the summary

【 Data structure and algorithm 】 Explain in detail what is a bidirectional linked list, and manually implement a bidirectional linked list structure with code

What is a bidirectional linked list

Two, the method of bidirectional linked list

Three, use code to achieve bidirectional linked list

Create a constructor

(2) Create an internal constructor

(3) Implement append() method

(4) Implement insert() method

(5) Implement get() method

(6) Implement indexOf() method

(7) Implement update()

Implement the removeAt() method

(9) Implement the remove() method

(10) Implement isEmpty()

(11) Implement the size() method

(12) Implement toString()

4. Supplement of bidirectional linked list

Five, the summary

Related Posts

Markdown to HTML document system

Promises – 3 minutes to master basic Promise principles

Uni-app differentiates the environment