This article was first published at www.shaotianyu.com
Advantages and disadvantages of arrays and linked lists
1.1 array (Array)
1.1.1 Advantages of arrays
A kind of linear list. In high-level data languages, there is no strict requirement for the type of elements inside an array, which is called generics in the language and can be put into any unit type. Array of the underlying hardware implementation, there is a memory manager, when applying for an array of computing opportunity opening a contiguous address in memory, each address can access through the memory manager, array access the first element and the time complexity of any other elements are the same, is O (1), namely the constant level. Because arrays can access any element randomly, they are time efficient, which is one of the advantages of arrays.
1.1.2 Disadvantages of arrays
The problem with an array is when it adds or removes elements.
For example, if you have an array and want to insert an element F in the middle, then elements C, D, and E should be moved back one position accordingly, so that the time complexity of the array insertion operation tends to be between O(1) and O(n). The same goes for array deletion.
Therefore, the disadvantages of arrays become apparent when the addition and deletion operations are frequent.
Here is the time complexity for each operation in the array:
| operation | Maximum time complexity |
|---|---|
| search | O(1) |
| insert | O(n) |
| remove/delete | O(n) |
| append | O(1) |
| prepend | O(1) |
1.2 linked list (LinkedList)
Singly linked lists
Unidirectional cyclic linked lists
1.2.1 Advantages of linked lists
Compared to an array, list on the increase and delete nodes, will not cause other group of moving nodes, then add, delete the time complexity of O (1), here is a singly linked list to insert a node of the schematic diagram, we can see that only need to change the current node and front nodes and the next pointer, can complete the insert of the node. The following is a schematic diagram of the node insertion operation of a single linked list:
1.2.2 Disadvantages of linked lists
Accessing the position of any element in a linked list is not as easy as an array. You need to start at the head of the list and work your way back, in this case between O(1) and O(n). Here is the time complexity of each operation in the linked list:
| operation | Maximum time complexity |
|---|---|
| search | O(n) |
| insert | O(1) |
| remove/delete | O(1) |
| append | O(1) |
| prepend | O(1) |
1.2.3, jump table
Since the time complexity of the search operation of the linked list is O(n), in order to make up for the defects of the linked list, we can consider adding multiple Pointers to the linked list as the starting Pointers, so that the search of a node will be more efficient and the time complexity of the search will be reduced.
Thus, the idea of skip table is introduced, and multiple starting Pointers are promoted to the concept of index. Time degree optimization is carried out by adding dimensions and changing space to time. The time complexity of search in skip table is O(logn).
The following is a schematic diagram of the first level index in a hop table:
Second, use JS to achieve the linked list
Understand the linked list of several general forms, we can use JS step by step to achieve the linked list of this data structure.
2.1. Single linked list
Singly linked lists are implemented by constantly updating the next pointer to a node to keep the list in series.
class Node {
constructor (element) {
this.element = element
this.next = null}}class LinkedList {
constructor () {
// Initializes the list length
this.length = 0
// Initializes the first node in the list
this.head = null
}
append (element) {
let node = new Node(element)
let current
// The linked list is empty
if (this.head === null) {
this.head = node
} else {
current = this.head
while (current.next) {
current = current.next
}
current.next = node
}
this.length ++
}
insert (element, point) {
if (point >=0 && point <= this.length) {
let node = new Node(element)
let current = this.head
let previous
let index = 0
if (point === 0) {
node.next = current
this.head = node
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = node
node.next = current
}
this.length++
return true
} else {
return false}}removeAt (point) {
if (point > -1 && point < this.length) {
let current = this.head
let index = 0
let previous
if (point= = =0) {
this.head = current.next
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
} else {
return null}}remove (element) {
let index = this.find(element)// The deleted node is returned after deletionreturn this.removeAt(index)}find (element) {
let current = this.head
let index = 0
if (element= =current.element){
return 0;
}
while (current.next) {
if(current.element= = =element) {
return index
}
index++
current = current.next
}
if (element= =current.element){
return index;
}
return - 1
}
isEmpty () {
return this.length= = =0
}
size () {
return this.length
}
print () {
let current = this.head
let result = ' '
while (current) {
result+ =current.element + (current.next ? '->' : '')
current = current.next
}
return result
}
}
let l1 = new LinkedList()
...
Copy the code2.2. Bidirectional linked lists
The principle of implementing the bidirectional linked list is that the next and prev Pointers should be taken into account every time the linked list is updated, and the updated Pointers should be pointed to.
class Node {
constructor (element) {
this.element = element
this.next = null
this.prev = null}}class DoubleLinkedList {
constructor () {
this.length = 0
this.head = null
// Define the tail node
this.tail = null
}
append (element) {
let node = new Node(element)
let tail = this.tail
if (this.head === null) {
this.head = node
this.tail = node
} else {
tail.next = node
node.prev = tail
this.tail = node
}
this.length++
}
insert (element, point) {
if(point >= 0 && point <= this.length) {
let node = new Node(element)
let current = this.head
let tail = this.tail
let index = 0
let previous
if (point === 0) {
if (!this.head) {
this.head = node
this.tail = node
} else {
node.next = current
current.prev = node
this.head = node
}
} else if (point === this.length) {
current = tail
current.next = node
node.prev = current
this.tail = node
} else {
while (index++ < point) {
previous = current
current = current.next} // Disconnect the original list and re-concatenate it using Pointersnode.next = current
node.prev = previous
previous.next = node
current.prev = node
}
this.length++
return true
} else {
return false}}removeAt (point) {
if (point > -1 && point < this.length) {
let current = this.head
let index = 0
let previous
let tail = this.tail
if (point= = =0) {
// removeThe first onethis.head = current.next
if (this.length= = =1) {
this.tail = null
} else {
this.head.prev = null}}else if (point= = =this.length - 1) {
current = tail
this.tail = current.prev
this.tail.next = null
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
this.length--
return current.element
} else {
return null}}find (element) {
let current = this.head
let index = 0
if (element= =current.element){
return 0;
}
while (current.next) {
if(current.element= = =element) {
return index
}
index++
current = current.next} // To ensure that the last bit is foundif (element= =current.element){
return index;
}
return - 1
}
remove (element) {
let index = this.find(element)
return this.removeAt(index)}isEmpty () {
return this.length= = =0
}
size () {
return this.length
}
print () {
let current = this.head
let result = ' '
while (current) {
result+ =current.element + (current.next ? '->' : '')
current = current.next
}
return result
}
}
let l1 = new DoubleLinkedList()
Copy the code2.3. One-way circular linked lists
The only difference is that the next pointer to the tail node points to the head, so that the end of the list is connected in series to form a loop.
class Node {
constructor (element) {
this.element = element
this.next = null}}class CircleLinkedList {
constructor () {
// Initializes the list length
this.length = 0
// Initializes the first node in the list
this.head = null
}
append (element) {
let node = new Node(element)
let head = this.head
let current
// The linked list is empty
if (this.head === null) {
this.head = node
} else {
current = this.head
while(current.next && current.next ! == head) { current = current.next } current.next = node }// Keep end to end
node.next = head
this.length ++
}
insert (element, point) {
if (point >=0 && point <= this.length) {
let node = new Node(element)
let current = this.head
let previous
let index = 0
if (point === 0) {
node.next = current
while(current.next && current.next ! = =this.head) {
current = current.next
}
this.head = node
current.next = this.head
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = node// end to endnode.next = current= = =null ? head : current
}
this.length++
return true
} else {
return false}}removeAt (point) {
if (point > -1 && point < this.length) {
let current = this.head
let index = 0
let previous
if (point= = =0) {
this.head = current.next
while (current.next && current.next! = =this.head) {
current = current.next
}
current.next = this.head
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
} else {
return null}}remove (element) {
let index = this.find(element)// The deleted node is returned after deletionreturn this.removeAt(index)}find (element) {
let current = this.head
let index = 0
if (element= =current.element){
return 0;
}
while (current.next && current.next! = =this.head) {
if(current.element= = =element) {
return index
}
index++
current = current.next
}
if (element= =current.element){
return index;
}
return - 1
}
isEmpty () {
return this.length= = =0
}
size () {
return this.length
}
print () {
let current = this.head
let result = ' '
while (current.next && current.next! = =this.head) {
result+ =current.element + (current.next ? '->' : '')
current = current.next
}
result += current.element
return result
}
}
let l1 = new CircleLinkedList()
Copy the code2.4. Bidirectional circular linked lists
The principle of a bidirectional circular list is roughly the same as that of a unidirectional circular list. The difference is that the bidirectional circular list has two Pointers prev and Next at the same time, and the Pointers are updated at the head and tail critical points, and the end of the list is maintained.
Third, summary
The above is my shallow understanding of the linked list array related data structure, if there is any mistake, please point out ~ ~
The above code is referenced in the book javascript Data Structures and Algorithms ~ ~
🍺 🍺 🍺 🍺 🍺