“This is the fifth day of my participation in the November Gwen Challenge. Check out the event details: The Last Gwen Challenge 2021

Compare unidirectional and bidirectional lists

Singly linked list

You can only go from the beginning to the end or from the end to the end.

  • In other words, this list is connected in one direction

  • The idea is that the last list has a reference to the next

Disadvantages of one-way linked lists

- It is easy to get to the next node, but difficult to get back to the last node. You have to start from scratch and go through it againCopy the code

Two-way linked list

  • You can go from the beginning to the end, and you can go from the end to the end

  • How it works: A node has both backward and forward references

  • Bidirectional linked lists can effectively solve problems in unidirectional linked lists

Disadvantages of bidirectional linked lists

- Four references need to be processed each time a node is inserted or deleted, which is more difficult to implement - takes up more memory space than a one-way linked listCopy the code

Characteristics of bidirectional linked lists

  • You can use a head and a tail to point to nodes at the head and tail, respectively

  • Each node consists of three parts: the pointer to the previous node (prev), the saved data (data), and the pointer to the next node (next).

  • The prev of the first node of the bidirectional list is null

  • Next is null for the last node of the bidirectional list

Common operations for bidirectional linked lists

  • Append (Element) : Adds a new item to the end of the list

  • Insert (position, element) : Inserts a new item into a specific position in the list

  • Get (position) : Obtains the element at the corresponding position

  • IndexOf (element) : returns the indexOf the element in the list, or -1 if there is none

  • Update (position, element) : Modifies an element in a position

  • RemoveAt (position) : Removes an item from a specific position in the list

  • Remove (element) : Removes an item from a list

  • IsEmpty () : checks whether the list isEmpty

  • Size () : Returns the number of elements in the list

  • ForwardString () : Returns a string of nodes traversed backwards

  • BackwardString () : Returns a string of nodes traversed backwards and forwards

  • toString()

  • GetHead () : Returns the first item in the list

  • GetTail: Returns the last item in the list

Bidirectional linked list code implementation

code

class DoublyLinkedListItem { data = undefined; prev = null next = null; constructor(data) { this.data = data; } } class DoublyLinkedList { head = null tail = null length = 0 append(data) { const newItem = new DoublyLinkedListItem(data); if(this.length === 0) { this.head = newItem this.tail = newItem } else { newItem.prev = this.tail this.tail.next = newItem this.tail = newItem } this.length += 1 } insert(position, data) { if(position < 0 || position > this.length) {return } const newItem = new DoublyLinkedListItem(data); if (this.length === 0) { this.head = newItem this.tail = newItem } else { if (position === 0) { newItem.next = this.head  this.head.prev = newItem this.head = newItem } else if (position === this.length) { newItem.prev = this.tail this.tail.next = newItem this.tail = newItem } else { let currentItem = this.head for(let i = 0; i < position; i ++) { currentItem = currentItem.next } newItem.prev = currentItem.prev newItem.next = currentItem currentItem.prev.next = newItem currentItem.prev = newItem } } this.length += 1 } get(position) { if(position < 0 || position >= this.length) {return null} let currentItem = this.head for(let i = 0; i < position; i++) { currentItem = currentItem.next } return currentItem.data } indexOf(data) { let currentItem = this.head for (let i = 0; i < this.length; i++) { if(currentItem.data === data) { return i } else { currentItem = currentItem.next if (currentItem === null) { return -1 } } } } update(position, newData) { if(position < 0 || position >= this.length) {return null} let currentItem = this.head for(let i = 0; i < position; i++) { currentItem = currentItem.next } currentItem.data = newData } removeAt(position) { if(position < 0 || position >=  this.length) {return } let currentItem = this.head if (this.length === 1) { this.head = null this.tail = null } else { if (position === 0) { this.head.next.prev = null this.head = this.head.next } else if (position === this.length - 1) { currentItem = this.tail this.tail.prev.next = null this.tail = this.tail.prev } else { for (let i = 0; i < position; i ++) { currentItem = currentItem.next } currentItem.prev.next = currentItem.next currentItem.next.prev = currentItem.prev } } this.length -= 1 return currentItem.data } remove(data) { const index = this.indexOf(data) return this.removeAt(index) } toString() { return this.backwardString() } forwardString() { let currentItem = this.tail let resultString = '' for(let i = 0; i < this.length; i ++ ){ resultString += currentItem.data + " " currentItem = currentItem.prev } return resultString } backwardString() {  let currentItem = this.head let resultString = '' for(let i = 0; i < this.length; i ++ ){ resultString += currentItem.data + " " currentItem = currentItem.next } return resultString } isEmpty() { return  this.length === 0 } size() { return this.length } getHead() { return this.head.data } getTail() { return this.tail.data }}Copy the code

The test code

const doublyLinkedList = new DoublyLinkedList()
doublyLinkedList.append('abc');
doublyLinkedList.append('cba');
doublyLinkedList.append('nba');
doublyLinkedList.append('ban');
console.log(doublyLinkedList.backwardString());     //abc cba nba ban
console.log(doublyLinkedList.forwardString());      //ban nba cba abc
console.log(doublyLinkedList.toString());           //abc cba nba ban
console.log(doublyLinkedList.size())                //4
console.log(doublyLinkedList.isEmpty())             //false
doublyLinkedList.update(3, 'bbb')                 
console.log(doublyLinkedList.removeAt(2));          //'nba'
console.log(doublyLinkedList.remove('nba'))         //undefined 
console.log(doublyLinkedList.toString());           //abc cba bbb
doublyLinkedList.insert(0, 'aaa')
doublyLinkedList.insert(5, 'ccc')
doublyLinkedList.insert(2, 'bbb')
console.log(doublyLinkedList.toString());           //aaa abc bbb cba bbb
console.log(doublyLinkedList.get(3));               // cba
console.log(doublyLinkedList.indexOf('abc'))        // 1
console.log(doublyLinkedList.getHead())             //aaa
console.log(doublyLinkedList.getTail())             //bbb
Copy the code