“This is my fourth day of the November Gwen Challenge. Check out the details: The Last Gwen Challenge 2021

Compare linked lists and array structures

Linked lists, like arrays, can be used to store a series of elements, but the implementation mechanism for linked lists and arrays is completely different

An array of

  • Arrays are probably the most common data structure for storing multiple elements
  • Almost every language implements array structures by default

Disadvantages:

  • The creation of an array usually requires a contiguous memory space (a whole block of memory) of a fixed length (in most programming languages, JS is not included). So when an array is not large enough, you need to expand it (usually by applying for a larger array and copying the elements of the original array).

  • Inserting data at the beginning or middle of an array is expensive and requires a lot of element displacement

The list

  • Another option for storing multiple elements is linked lists

  • Unlike arrays, the elements in a linked list need not be contiguous in memory

  • Each element of a linked list consists of a node that stores the element itself and a reference to the next element

Advantages:

  • Memory space does not have to be contiguous. The memory of the computer can be fully utilized to achieve flexible dynamic memory management

  • Lists no longer have to be sized when they are created, and the size can be extended indefinitely

  • The time complexity of linked list can reach O(1) when inserting and deleting data, which is much more efficient than array

Disadvantages:

  • When a linked list accesses an element at any location, it needs to be accessed from scratch (you cannot skip the first element to access subsequent elements). Arrays, on the other hand, can access elements at any location through subscripts

  • Instead of accessing elements directly by subscript, you need to access them one by one until you find the response element

What is a linked list? (One-way linked list)

A linked list can be analogous to a train, where there is a locomotive connected to the next car, which has passengers (i.e. data), which is connected to the next car, and so on.

Schematic diagram

A linked list can be analogous to a train, where there is a locomotive connected to the next car, which has passengers (i.e. data), which is connected to the next car, and so on.

Common operations for one-way 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

  • toString()

Encapsulates a one-way linked list object

code

class LinkedListItem { data = undefined; next = null; constructor(data) { this.data = data; } } class LinkedList { head = null; length = 0; append(data) { const newItem = new LinkedListItem(data); if (this.length === 0) { this.head = newItem; } else { let currentItem = this.head; while (currentItem.next) { currentItem = currentItem.next; } currentItem.next = newItem; } this.length += 1; } insert(position, data) { if (position < 0 || position > this.length) {return false; } const newItem = new LinkedListItem(data); if (position === 0) { newItem.next = this.head; this.head = newItem; } else { let currentItem = this.head; for (let i = 0; i < position - 1; i++) { currentItem = currentItem.next; } newItem.next = currentItem.next; currentItem.next = newItem; } this.length += 1; return true; } 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 (data === currentItem.data) { return i; } else { currentItem = currentItem.next; if (currentItem === null) {return -1; } } } } update(position, newData) { if (position < 0 || position >= this.length) return; 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( position === 0) { this.head = this.head.next } else { for(let i = 0; i < position - 1; i ++) { currentItem = currentItem.next } currentItem.next = currentItem.next.next } this.length -= 1 } remove(data) { const index = this.indexOf(data) this.removeAt(index) } isEmpty() { return this.length === 0 } size() { return this.length } toString() { let currentItem = this.head; let resultString = ''; while (currentItem) { resultString += currentItem.data + ' '; currentItem = currentItem.next; } return resultString; }}Copy the code

The test code

const linkedList = new LinkedList(); console.log(linkedList.isEmpty()) // true linkedList.append('abc'); linkedList.append('cba'); linkedList.append('nba'); linkedList.append('ban'); console.log('linkedList', linkedList.toString()); // 'abc cba nba ban' linkedList.update(2, '111') // 'abc cba' console.log(linkedList.indexOf('cba')); // 1 linkedList.insert(3, 'ccc') linkedList.removeAt(3) console.log(linkedList.isEmpty()) // false console.log(linkedList.size()) // 4 console.log(linkedList.remove('nba')) console.log('linkedList', linkedList.toString()); // 'abc cba 111 ban' console.log(linkedList.get(2)); / / '111'Copy the code