This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!
preface
This article introduces the “linked list” structure and uses JS code to implement the corresponding structure.
introduce
A linked list is a data structure composed of nodes, and nodes are generally composed of data and a “pointer” to record the address of the next node (two-way linked lists also have a “pointer” to record the address of the previous node).
There are many kinds of lists.
- Singly linked lists
- Circular list (or unidirectional circular list)
- Two-way linked list
- Two-way circular list
- Lead list (acyclic list with sentinel nodes)
Note: several terms will be used in this article. We generally call the next node of a node a “successor node”, and the “pointer” of a node that records the address of the next node a “successor pointer”; The previous node of the node is called the “precursor node”, and the “pointer” of the node that records the address of the previous node is called the “precursor pointer”.
Singly linked lists
A singly linked list has two special nodes: the head node and the tail node.
The header node records the initial address and is not pointed to by any “successor pointer” to the node.
The tail node records the last address, and the “successor pointer” points to null.
Note: The list code below records the end node. In fact, you can implement the list structure without recording the end node at all.
Js code implementation
/ / node
class Node {
constructor(data) {
this.data = data
this.next = null}}/ / singly linked lists
class LinkedList {
#size = 0 // List length
#head = null / / head node
#tail = null / / end nodes
/* 增 */
// Add a node to the end
append(data) {
let node = new Node(data)
if (this.#tail) {
this.#tail.next = node
this.#tail = node
} else {
this.#head = node
this.#tail = node
}
this.#size++
}
// Add nodes based on location (location is 0)
insert(index, data) {
if (index > this.#size || index < 0) {
return false
}
let node = new Node(data)
if (this.#size === 0) {
// Insert directly without length
this.#head = node
this.#tail = node
} else if (index == this.#size) {
// End node, special operation
this.#tail.next = node
this.#tail = node
} else if (index == 0) {
// Head node, special operation
node.next = this.#head
this.#head = node
} else {
// There must be intermediate nodes
let target = this.#head
let prev = null
for (let i = 1; i <= index; i++) {
prev = target
target = target.next
}
node.next = target
prev.next = node
}
this.#size++
return true
}
/ * * / delete
// Delete the node closest to the relevant value
delete(data) {
let node = this.#head
let prev = null
while (node) {
if (node.data === data) {
if (node === this.#head) { // The node to be deleted is the head node, which needs to be changed
if (this.#head === this.#tail) {
this.#head = null
this.#tail = null
} else {
this.#head = this.#head.next
}
} else if (node === this.#tail) { // The deleted node is the tail node, and the tail node needs to be changed
prev.next = null
this.#tail = prev
} else {
prev.next = node.next
}
this.#size--
return true
} else {
prev = node
node = node.next
}
}
return false
}
// Delete nodes at relevant locations
deleteIndex(index) {
if (index > this.#size - 1 || index < 0) {
return false
}
if (index === 0) { // Delete the header node
if (this.#head === this.#tail) {
this.#head = null
this.#tail = null
} else {
this.#head = this.#head.next
}
} else {
let node = this.#head
let prev = null
for (let i = 1; i <= index; i++) {
prev = node
node = node.next
}
if (node === this.#tail) {
prev.next = null
this.#tail = prev
} else {
prev.next = node.next
}
}
this.#size--
return true
}
/* 查 */
// List length
size() {
return this.#size
}
// Get the header node
head() {
return this.#head
}
// Get the tail node
tail() {
return this.#tail
}
// Find the node that first appeared
find(data) {
let node = this.#head
while (node) {
if (node.data === data) {
return node
} else {
node = node.next
}
}
}
// Find the node by location (location is 0)
findIndex(index) {
if (index > this.#size - 1 || index < 0) {
return
}
if (index == 0) {
return this.#head
}
if (index == this.#size - 1) {
return this.#tail
}
let node = this.#head
for (let i = 1; i <= index; i++) {
node = node.next
}
return node
}
// Find the first occurrence of the value (position is 0)
indexOf(data) {
let node = this.#head
let i = 0
while (node) {
if (node.data === data) {
return i
} else {
node = node.next
i++
}
}
return -1
}
// Whether to be empty
isEmpty() {
return this.#size === 0 ? true : false
}
// Print (from beginning to end)
print() {
if (this.#size === 0) {
console.log('Empty list, head node:'.this.#head, 'Tail node:'.this.#tail)
return
}
let node = this.#head
while (node) {
console.log(node.data)
node = node.next
}
console.log('Head node:'.this.#head)
console.log('Tail node:'.this.#tail)
console.log(Total length: + this.#size)
}
}
Copy the codeUnidirectional circular linked list
The unidirectional circular list is derived from the single linked list. The difference is that the end node of the unidirectional circular list no longer points to null, but to the head node, forming a ring structure.
This structure is particularly useful for solving the Joseph problem.
Js code implementation
/ / node
class Node {
constructor(data) {
this.data = data
this.next = null}}// Circular list
class CircleLinkedList {
#size = 0 // List length
#head = null / / head node
#tail = null / / end nodes
/* 增 */
// Add a node to the end
append(data) {
let node = new Node(data)
if (this.#tail) {
this.#tail.next = node
this.#tail = node
// Reconnect the end node to the end node
this.#tail.next = this.#head
} else {
this.#head = node
this.#tail = node
this.#tail.next = this.#head
}
this.#size++
}
// Add nodes based on location (location is 0)
insert(index, data) {
if (index > this.#size || index < 0) {
return false
}
let node = new Node(data)
if (this.#size === 0) {
// Insert directly without length
this.#head = node
this.#tail = node
} else if (index == this.#size) {
// End node, special operation
this.#tail.next = node
this.#tail = node
this.#tail.next = this.#head
} else if (index == 0) {
// Head node, special operation
node.next = this.#head
this.#head = node
this.#tail.next = this.#head
} else {
// There must be intermediate nodes
let target = this.#head
let prev = null
for (let i = 1; i <= index; i++) {
prev = target
target = target.next
}
node.next = target
prev.next = node
}
this.#size++
}
/ * * / delete
// Delete the node closest to the relevant value
delete(data) {
let node = this.#head
let prev = null
while (node) {
if (node.data === data) {
if (node === this.#head) {
// The node to be deleted is the head node, which needs to be changed
if (this.#head === this.#tail) {
this.#head = null
this.#tail = null
node.next = null
} else {
this.#head = node.next
this.#tail.next = this.#head
}
} else if (node === this.#tail) {
// The deleted node is the tail node, and the tail node needs to be changed
prev.next = this.#head
this.#tail = prev
} else {
prev.next = node.next
}
node.next = null // Set next to null for the node to be deleted
this.#size--
return true
} else {
if (node === this.#tail) {
break
}
prev = node
node = node.next
}
}
return false
}
// Delete nodes at relevant locations
deleteIndex(index) {
if (index > this.#size - 1 || index < 0) {
return false
}
if (index === 0) {
if (this.#head === this.#tail) {
this.#head = null
this.#tail = null
} else {
this.#head = this.#head.next
this.#tail.next = this.#head
}
} else {
let node = this.#head
let prev = null
for (let i = 1; i <= index; i++) {
prev = node
node = node.next
}
if (node === this.#tail) {
prev.next = this.#head
this.#tail = prev
} else {
prev.next = node.next
}
node.next = null
}
this.#size--
return true
}
/* 查 */
// List length
size() {
return this.#size
}
// Get the header node
head() {
return this.#head
}
// Get the tail node
tail() {
return this.#tail
}
// Find the node that first appeared
find(data) {
let node = this.#head
while (node) {
if (node.data === data) {
return node
} else if (node === this.#tail) {
break
} else {
node = node.next
}
}
}
// Find the node by location (location is 0)
findIndex(index) {
if (index > this.#size - 1 || index < 0) {
return
}
if (index == 0) {
return this.#head
}
if (index == this.#size - 1) {
return this.#tail
}
let node = this.#head
for (let i = 1; i <= index; i++) {
node = node.next
}
return node
}
// Find the first occurrence of the value (position is 0)
indexOf(data) {
let node = this.#head
let i = 0
while (node) {
if (node.data === data) {
return i
} else if (node === this.#tail) {
break
} else {
node = node.next
i++
}
}
return -1
}
// Whether to be empty
isEmpty() {
return this.#size === 0 ? true : false
}
// Print (from beginning to end)
print() {
if (this.#size === 0) {
console.log('Empty list, head node:'.this.#head, 'Tail node:'.this.#tail)
return
}
let node = this.#head
while (node) {
console.log(node.data)
if (node === this.#tail) {
break
} else {
node = node.next
}
}
console.log('Head node:'.this.#head)
console.log('Tail node:'.this.#tail)
console.log('Is the node next to the tail node the head node?'.this.#head === this.#tail.next)
console.log(Total length: + this.#size)
}
}
Copy the codeTwo-way linked list
Compared with the unidirectional linked list, the bidirectional linked list has a “precursor pointer”, which is used to record the address of the previous node. Because the bidirectional linked list has both a “precursor pointer” and a “successor pointer”, the bidirectional linked list takes up much more memory than the unidirectional linked list. However, even if bidirectional linked lists take up more memory, we prefer to use this structure in development, because this structure can find nodes forward, finding data is more efficient than unidirectional linked lists, and in some insert or delete operations, it is much easier to manipulate the previous node to connect to another node. A bidirectional linked list is a typical “space for time” structure.
Note here that the following method, findIndex, no longer blindly traverses from beginning to end like a single linked list. Since the bidirectional list can be traversed from the end to the end, here first determine whether the index is less than size/2, if less than, then traversal from the beginning to the end, if greater than, then traversal from the end to the end.
Js code implementation
// Add a pointer to the node
class Node {
constructor(data) {
this.data = data
this.next = null
this.prev = null}}// Two-way linked list
class DoubleLinkedList {
#size = 0 // List length
#head = null / / head node
#tail = null / / end nodes
/* 增 */
// Add a node to the end
append(data) {
let node = new Node(data)
if (this.#tail) {
this.#tail.next = node
node.prev = this.#tail
this.#tail = node
} else {
this.#head = node
this.#tail = node
}
this.#size++
}
// Add nodes based on location (location is 0)
insert(index, data) {
if (index > this.#size || index < 0) {
return false
}
let node = new Node(data)
if (this.#size === 0) {
// Insert directly without length
this.#head = node
this.#tail = node
} else if (index == this.#size) {
console.log(123)
// End node, special operation
node.prev = this.#tail
this.#tail.next = node
this.#tail = node
} else if (index == 0) {
// Head node, special operation
this.#head.prev = node
node.next = this.#head
this.#head = node
} else {
// There must be intermediate nodes
let target = this.#head
for (let i = 1; i <= index; i++) {
target = target.next
}
node.next = target
node.prev = target.prev
target.prev.next = node // Note this step
target.prev = node
}
this.#size++
return true
}
/ * * / delete
// Delete the node closest to the relevant value
delete(data) {
let node = this.#head
while (node) {
if (node.data === data) {
if (node === this.#head) { // The node to be deleted is the head node, which needs to be changed
if (this.#head === this.#tail) {
this.#head = null
this.#tail = null
} else {
this.#head = this.#head.next
this.#head.prev = null}}else if (node === this.#tail) { // The deleted node is the tail node, and the tail node needs to be changed
node.prev.next = null
this.#tail = node.prev
} else {
node.next.prev = node.prev
node.prev.next = node.next
}
this.#size--
return true
} else {
node = node.next
}
}
return false
}
// Delete nodes at relevant locations
deleteIndex(index) {
if (index > this.#size - 1 || index < 0) {
return false
}
if (index === 0) { // Delete the header node
if (this.#head === this.#tail) {
this.#head = null
this.#tail = null
} else {
this.#head = this.#head.next
this.#head.prev = null}}else if (index === this.#size-1) { // Delete the tail node
this.#tail.prev.next = null
this.#tail = this.#tail.prev
} else {
// let node = this.#head
// for (let i = 1; i <= index; i++) {
// node = node.next
// }
let node = this.findIndex(index)
if (node) {
node.next.prev = node.prev
node.prev.next = node.next
} else {
return false}}this.#size--
return true
}
/* 查 */
// List length
size() {
return this.#size
}
// Get the header node
head() {
return this.#head
}
// Get the tail node
tail() {
return this.#tail
}
// Find the node that first appeared
find(data) {
let node = this.#head
while (node) {
if (node.data === data) {
return node
} else {
node = node.next
}
}
}
// Find the node by location (location is 0)
findIndex(index) {
if (index > this.#size - 1 || index < 0) {
return
}
if (index == 0) {
return this.#head
}
if (index == this.#size - 1) {
return this.#tail
}
// If index is to the left or right of size/2, you can find the data faster
let node
if (index < this.#size/2) {
node = this.#head
for (let i = 1; i <= index; i++) {
node = node.next
}
} else {
node = this.#tail
for (let i = this.#size-1; i > index; i--) {
node = node.prev
}
}
return node
}
// Find the first occurrence of the value (position is 0)
indexOf(data) {
let node = this.#head
let i = 0
while (node) {
if (node.data === data) {
return i
} else {
node = node.next
i++
}
}
return -1
}
// Whether to be empty
isEmpty() {
return this.#size === 0 ? true : false
}
// Print (isPrev: false, start to end; True, from end to end)
print(isPrev) {
if (this.#size === 0) {
console.log('Empty list, head node:'.this.#head, 'Tail node:'.this.#tail)
return
}
if(! isPrev) {console.log('Print from beginning to end')
let node = this.#head
while (node) {
console.log(node.data)
node = node.next
}
} else {
console.log('Print from end to end')
let node = this.#tail
while(node) {
console.log(node.data)
node = node.prev
}
}
console.log('Head node:'.this.#head)
console.log('Tail node:'.this.#tail)
console.log(Total length:.this.#size)
}
}
Copy the codeTwo-way circular list
Similar to unidirectional linked list, bidirectional circular linked list is based on bidirectional linked list, and the “successor pointer” of the tail node points to the head node.
Look at the above unidirectional circular linked list and two-way linked list, I believe you have a two-way circular linked list has a certain idea, here is not implemented.
Leading the list
In both unidirectional and bidirectional lists, insert a new head node and delete a new head node. (Circular lists are not considered here, because circular lists have no boundaries.)
Singly linked list, for example, our normal insert operation, is the previous node “subsequent Pointers point to the new node, the new node of the” subsequent Pointers point to the next node, but if the insert is the new head node, because before a node does not exist, we only need the new head node “subsequent pointer pointing to the original head node.
The normal deletion operation is to point the “successor pointer” of the previous node to the next node to be deleted. However, if the node to be deleted is the head node, since the previous node does not exist, we only need to refer the head node to the next node of the original head node.
Now, some people might wonder, is there a special operation for inserting or deleting a tail node?
Don’t.
Insert the end node node operation, pseudocode
node.next = tail.next // First, the new tail node's "successor pointer" points to the node next to the original tail node, which is null
tail.next = node // Then point the original tail node "successor pointer" to the new tail node
Copy the codeThis operation is exactly the same as inserting a new node in the middle of the list, except that the “successor pointer” to the last node of the new insertion will point to null instead of a node. But if you’re writing code that needs to keep track of the tail node at all times, as I did above, and your LinkedList has both #head and #tail, you do need a little extra operation to point #tail to the new tail node. In fact, you can write your list without having to keep track of the tail node at all times.
Get back to business, due to the boundary problems, it is easy to miss mistakes when writing code, so it can be joined a special nodes “sentinel node” to solve the problem of the boundary, the sentinel node “” subsequent pointer pointing to the head node, therefore” sentinel node “instead of the original head node, as the new head node, The Sentinel node does not store any data; its data is always null.
Let’s look at the insert operation. If I want to insert the first new node with data, we need to point the sentinel’s successor pointer to the new node, which points to the original first node with data. Is this exactly the same as inserting a new node in the middle of the list?
Delete the same, here do not do detailed description.
Code implementation is also very simple, as long as the above unidirectional linked list based on a slightly modified, the original head node to sentinel node, and then a little change, here is not implemented.
practice
List although is a very basic structure, and I’ve used the Java language to realize again, but I still problems in the process of writing, it took me some time to debug, these errors included “border didn’t handle”, and “pointer refers to the right place”, “forget to put on a node pointer refers to the new nodes” and so on.
I have made a small summary, I hope to be useful to you, when writing a linked list, pay attention to the following points:
- Singly linked lists
- Insert or delete header nodes
- When you have only one node and you want to delete that node, you assign null to both the head node and the tail node
- Circular linked list
- Insert or delete a head node, noting the connection between the head node and the tail node
- Inserting or deleting a tail node, note the connection between the head node and the tail node
- When iterating through the data, be careful to avoid an infinite loop and break out of the loop when you hit the tail node
- Two-way linked list
- Delete or insert the middle node, notice the next and prev pointing, can first draw in the notebook, with arrows to show the relationship between nodes, which relationship to cut off, which relationship to connect
- Because bidirectional lists can find nodes forward, some query operations can be optimized (such as findIndex for “bidirectional lists” above)
Common progress
Welcome to like, follow, collect and share. If there are any mistakes, please go to the comments section to correct them. Without authorization, reproduction is strictly prohibited. If you need to reproduce, please contact me for authorization. O ~) ~)o