### The introduction

Linked lists are much more complex than arrays. First of all, linked lists do not require contiguous memory space. They are made up of a group of discrete memory blocks connected by Pointers. The most common types of linked lists are single, double, and circular.

The most important thing to learn a linked list is to draw lots of pictures and practice. There is no shortcut to follow. When faced with a linked list problem, Aquarius summarized the following five steps:

- Determine the data structure to solve the problem: single, double, or circular lists, etc
- Decide on the solution: How to solve the problem
- Drawing realization: Drawing can help us find the loophole in our thinking (some thinking is not perfect)
- Determine boundary conditions: Consider whether there are boundary problems in the solution and how to solve them
- Code implementation: solve the problem to complete ✅

This article will give the common linked list (single linked list, double linked list and circular linked list) of the basic operation has been code implementation, and give the implementation ideas, these are linked list solution cornerstone, please be sure to master! ⛽ ️ ⛽ ️ ⛽ ️

A bonus leetcode question at the end!

Let’s start this section!! 👇 👇 👇

### A single linked list

Single linked list structure:

```
function List () {
/ / the node
let Node = function (element) {
this.element = element
this.next = null
}
// The initial head node is null
let head = null
// List length
let length = 0
/ / operation
this.getList = function() {return head}
this.search = function(list, element) {}
this.append = function(element) {}
this.insert = function(position, element) {}
this.remove = function(element){}
this.isEmpty = function(){}
this.size = function(){}}Copy the code
```

#### 1. Add nodes:

** Determine the data structure to solve the problem: ** single linked list

Initialize a node (to be appended), traverse to the end of the chain, and insert the node after the end node

**Drawing implementation:**

Determine boundary conditions: When the linked list is null, head points directly to the node to be inserted without traversal

**Code implementation:**

```
function append (element) {
let node = new Node(element),
p = head
if(! head){ head = node }else {
while (p.next) {
p = p.next
}
p.next = node
}
length += 1
}
/ / test
let list = new List()
for(let i = 0; i < 5; i+=1) {
list.append(i)
}
Copy the code
```

Solve the problem ✅

#### 2. Look for:

Determine the data structure to solve the problem: single linked list

If the value of the node is equal to the value to be searched, return true; otherwise, continue to traverse the next node, until the whole list is not found, return false

Drawing realization: very simple, the reader can try to draw

Determine boundary conditions: When the linked list is NULL, false can be returned

**Code implementation:**

```
// Check whether a node exists in the list
function search(element) {
let p = head
if(! p)return false
while(p) {
if (p.element === element) return true
p = p.next
}
return false
}
/ / test
list.search(4) // true
list.search(11) // false
Copy the code
```

Solve the problem ✅

#### 3. Insert:

Determine the data structure to solve the problem: single linked list

Initialize a node (node to be inserted), traverse to the node before position, and insert the node after the node

**Drawing implementation:**

**Determine boundary conditions:**

- when
`position`

为`0`

, the node will be inserted directly`node.next`

Point to the`head`

，`head`

Point to the`node`

Ok, no need to traverse - When to insert position
`position < 0`

Or exceed the list length`position > length`

, are problematic, cannot be inserted, at this point directly return`null`

, failed to insert

**Code implementation:**

```
// Inserts the successor node of position
function insert (position, element) {
// Create an insert node
let node = new createNode(element)
if (position >= 0 && position <= length) {
let prev = head,
curr = head,
index = 0
if(position === 0) {
node.next = head
head = node
} else {
while(index < position) {
prev = curr
curr = curr.next
index ++
}
prev.next = node
node.next = curr
}
length += 1
} else {
return null}}/ / test
list.insert(10)
Copy the code
```

Solve the problem ✅

#### 4. Delete:

Determine the data structure to solve the problem: single linked list

Determine the solution idea: traverse the single linked list, find the node to be deleted, delete

**Drawing implementation:**

Determine boundary conditions: When the list is null, return

**Code implementation:**

```
// Delete the element node
function remove (element) {
let p = head, prev = head
if(! head)return
while(p) {
if(p.element === element) {
p = p.next
prev.next = p
} else {
prev = p
p = p.next
}
}
}
Copy the code
```

Solve the problem ✅

#### 5. Complexity Analysis

**Search: Search from the beginning node, time complexity O(n)**

**Insert or delete: The time complexity of inserting or deleting a node (successor node) after a node is O(1)**

Linked list five steps is not very easy to use 😊, the following look at the double linked list 👇

### Double linked lists

As the name implies, a singly linked list has only one direction, from the beginning node to the end node. Then a doubly linked list has two directions, from the end node to the end node:

```
function DoublyLinkedList() {
let Node = function(element) {
this.element = element
// Precursors
this.prev = null
// Next pointer
this.next = null
}
// The initial head node is null
let head = null
// Add a tail node
let tail = null
// List length
let length = 0
/ / operation
this.search = function(element) {}
this.insert = function(position, element) {}
this.removeAt = function(position){}
this.isEmpty = function(){ return length === 0 }
this.size = function(){ return length }
}
Copy the code
```

#### 1. Insert node in position:

Determine the data structure to solve the problem: double linked lists

Initialize a node (node to be inserted), traverse the linked list to the node before position, and insert the node after the node position

**Drawing implementation:**

**Determine boundary conditions:**

If the position to be inserted is position < 0 or exceeds the length of the linked list position > length, the insert cannot be inserted. In this case, null is returned directly, and the insert fails

**Code implementation:**

```
// Inserts the successor node of position
function insert (position, element) {
// Create an insert node
let node = new Node(element)
if (position >= 0 && position < length) {
let prev = head,
curr = head,
index = 0
if(position === 0) {
// Add in the first position
if(! head) {// Note that this is different from singly linked lists
head = node
tail = node
} else {
/ / the bidirectional
node.next = head
head.prev = node
// head points to the new head node
head = node
}
} else if(position === length) {
// Insert to the tail node
curr = tial
curr.next = node
node.prev = curr
// tail points to the new tail node
tail = node
} else {
while(index < position) {
prev = curr
curr = curr.next
index ++
}
// Insert after prev and before curr
prev.next = node
node.next = curr
curr.prev = node
node.prev = prev
}
length += 1
return true
} else {
return false}}/ / test
list.insert(10)
Copy the code
```

Solve the problem ✅

#### 2. Delete the:

Determine the data structure to solve the problem: double linked lists

Determine the solution idea: traverse the double-linked list, find the node to be deleted, delete

**Drawing implementation:**

Determine boundary conditions: When the list is null, return

**Code implementation:**

```
// Delete the node in position
function removeAt (position) {
if (position >= 0 && position < length && length > 0) {
let prev = head,
curr = head,
index = 0
if(position === 0) {
// Remove the head node
if(length === 1) { // There is only one node
head = null
tail = null
} else {
head = head.next
head.prev = null}}else if(position === length- 1) {
// Remove the tail node
curr = tial
tail = curr.prev
tail.next = null
} else {
while(index < position) {
prev = curr
curr = curr.next
index ++
}
/ / remove the curr
prev.next = curr.next
curr.next.prev = prev
}
length -= 1
return curr.element
} else {
return null}}Copy the code
```

Solve the problem ✅

#### 3. Look for:

A double-linked list lookup is similar to a single-linked list in that it iterates through the list and returns true if found, false if not found.

#### 4. Complexity Analysis

**Search: Search forerunner node or successor node time complexity is O(1), other nodes are still O(n)**

**Insert or delete: Insert or delete the time complexity of precursor node or successor node is O(1).**

### Circular singly linked lists

A circular singly linked list is a special singly linked list. The only difference between a singly linked list and a singly linked list is that the tail of the singly linked list points to NULL, while the tail of a circular singly linked list points to the head, which forms a end to end loop:

Since there are cyclic singly linked lists, there are also cyclic doubly linked lists, and the difference between a cyclic doubly linked list and a doubly linked list is:

- Double linked list
`tail.next`

(`tail`

Is the successor pointer to`null`

Circular double linked list`tail.next`

为`head`

- Double linked list
`head.prev`

(`head`

Is the precursor pointer to`null`

Circular double linked list`head.prev`

为`tail`

Take a circular single column table as an example

```
function CircularLinkedList() {
let Node = function(element) {
this.element = element
// Next pointer
this.next = null
}
// The initial head node is null
let head = null
// List length
let length = 0
/ / operation
this.search = function(element) {}
this.insert = function(positon, element) {}
this.removeAt = function(position){}
this.isEmpty = function(){ return length === 0 }
this.size = function(){ return length }
}
Copy the code
```

#### 1. Insert after positon:

Determine the data structure for the solution: circular singly linked lists

Initialize a node (node to be inserted), traverse to the node before position, and insert the node after the node

**Drawing implementation:**

**Determine boundary conditions:**

- when
`position`

为`0`

, you need to traverse to the tail node, and then insert the node after the tail node, and change the`head`

Point to the - When to insert position
`position < 0`

Or exceed the list length`position > length`

, are problematic, cannot be inserted, at this point directly return`null`

, failed to insert

**Code implementation:**

```
// Inserts the successor node of position
function insert (position, element) {
// Create an insert node
let node = new createNode(element)
if (position >= 0 && position <= length) {
let prev = head,
curr = head,
index = 0
if(position === 0) {
// Different from single linked list inserts
while(index < length) {
prev = curr
curr = curr.next
index ++
}
prev.next = node
node.next = curr
head = node
} else {
while(index < position) {
prev = curr
curr = curr.next
index ++
}
prev.next = node
node.next = curr
}
length += 1
} else {
return null}}/ / test
list.insert(10)
Copy the code
```

Solve the problem ✅

#### 2. Look for:

This is similar to single-linked lists except that index++ < length is the end of the loop condition

```
// Check whether a node exists in the list
function search(element) {
if(! head)return false
let p = head, index = 0
// The difference between a single list and a single list
while(index++ < length) {
if (p.element= = =element) return true
p = p.next
}
return false} / / testlist.search(4) / /true
list.search(11) / /false
Copy the code
```

Solve the problem ✅

#### 3. Delete:

This is similar to single-linked lists except that index++ < length is the end of the loop condition

```
// Delete the element node
function remove (element) {
let p = head, prev = head, index = 0
/ / an empty list
if(! head || )return
// There is only one node and element is the same
if(length === 1 && head.element === element){
head = null
length--
return
}
while(index++ < length) {
if(p.element= = =element) {
p = p.next
prev.next = p
length --
} else {
prev = p
p = p.next}}}Copy the code
```

Solve the problem ✅

#### 4. Complexity analysis

**Search: The circular list starts from any node to find the target node in O(n) time.**

**Insert or delete: It is the same as a single linked list, and the time complexity of insert and delete of subsequent nodes is O(1).**

### Leetcode21: merge two ordered lists

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

**Example:**

```
Input:1->2->4.1->3->4Output:1->1->2->3->4->4
Copy the code
```

Please submit your answers to github.com/sisterAn/Ja… “, so that more people can see, Aquarius will post his own solution tomorrow.

### Five, past series

Front-end advanced algorithm 3: Learning the LRU algorithm from the browser cache elimination strategy and Vue’s keep-alive

Bottle jun front-end advanced algorithm camp first week summary

Front-end advanced algorithm 2: JavaScript array from Chrome V8 source code

Front-end advanced algorithm 1: How to analyze and count the execution efficiency and resource consumption of algorithms?

### Six, know more front-end road friends, together with advanced front-end development

The first phase of front-end algorithm training camp is free 🎉🎉🎉, free yo!

Here, you can advance the front-end algorithm with like-minded friends (200+), from 0 to 1 to build a complete data structure and algorithm system.

Here, I not only introduce algorithms, but also combine algorithms with various front-end areas, including browsers, HTTP, V8, React, Vue source code, and so on.

Here, you can learn a big factory algorithm (Ali, Tencent, Baidu, byte, etc.) or leetcode every day, Aquarius will solve it the next day!

More benefits waiting for you to unlock 🔓🔓🔓!

Scan code to join [front-end algorithm exchange group exchange group], if the number of TWO-DIMENSIONAL code has reached the upper limit, you can scan the bottom two-dimensional code, in the public number “front-end bottle jun” reply “algorithm” automatically pull you into the group learning