部分图和题解来自：https://programmercarl.com/

链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

单链表

单链表是一种链式存取的数据结构，链表中的数据是以结点来表示的，每个结点由数据域和指针域构成。

链表1

单链表的常见操作

  1. append(value) ：向链表尾部添加新节点

  2. removeAt(index)：根据索引移除节点，返回数据域

链表-删除节点

  1. insert(index,value): 向链表的特定位置插入新节点，返回boolean值

链表-添加节点

  1. get(index): 获取对应索引的节点

  2. indexOf(value): 返回元素在链表中的索引。如果没有该元素返回 -1

  3. update(index,value) : 修改某个位置的元素，返回boolean值

  4. isEmpty()：链表是否为空

  5. size()：返回链表包含的元素个数。

  6. toString()： 由于链表使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，链表转字符串

单链表的定义

符号说明：

current：暂存当前节点

preNode：暂存当前节点的前一节点

position：当前节点索引

value：节点数据域

next：节点下一节点指针

head：链表头指针

length：链表长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// 定义节点
class Node {
    constructor(val) {
        this.value = val;  // 数据域
        this.next = null;  // 指针域
    }
}
// 定义链表
class LinkedList {
    constructor(){
        this.head = null; // 链表头指针
        this.length = 0;  // 链表长度
    }
    
    // 向链表尾部添加新节点
    append(value){
        let node = new Node(value);
        let current; // 暂存当前节点
        if (this.head === null) { //头节点为空
            this.head = node;
        } else {
            current = this.head;
            while (current.next) { // 遍历查询链表尾部
                current = current.next;
            }
            current.next = node;
        }
        this.length++;
    }
    
    // 根据索引移除节点，返回数据域
    removeAt(index) {
        if (index < 0 || index >= this.length) return null;
        let preNode;
        let current = this.head;
        let position = 0;
        if (index === 0) { // 删除头节点
            this.head = current.next;
        } else {
            while (position < index) {
                preNode = current;
                current = current.next;
                position++;
            }
            preNode.next = current.next; // 前节点指针域指向当前节点的下一个节点
        }
        this.length--;
        return current.value;
    }
    
    // 向链表的特定位置插入新节点，返回Boolean值
    insert(index,value){
        if (index < 0 || index > this.length) return false;
        let node = new Node(value);
        let current = this.head;
        let preNode;
        let position = 0;
        if (index === 0) {
            node.next = current;
            this.head = node;
        } else {
            while (position < index) {
                preNode = current;
                current = current.next;
                position++;
            }
            node.next = current;  // 先将新节点的指针域指向当前节点
            preNode.next = node;  // 再更新前一节点的指针域指向新节点
        }
        this.length++;
        return true;
    }
    
    // 获取对应索引的节点数据域
    getAt(index) {
        if (index < 0 || index >= this.length) {
            return null;
        }
        let position = 0;
        let current = this.head;
        while (position < index) {
            current = current.next;
            position++;
        }
        return current.value; // 返回数据域
    }
    
    // 返回元素在链表中的索引。如果没有该元素返回 -1
    indexOf(value) {
        if (this.length === 0) return -1;
        let current = this.head;
        let position = 0;
        while (position < this.length) {
            if (current.value == value) {
                return position; // 返回索引
            }
            current = current.next;
            position++;
        }
        return -1;  // 查找失败
    }
    
    // 修改某个位置的元素
    update(index,value) {
        if (index < 0 || index >= this.length) return false;
        let position = 0;
        let current = this.head;
        while (position < index) {
            current = current.next;
            position++;
        }
        current.value = value; // 更新值
        return true;
    }
    
    // 链表是否为空
    isEmpty() {
        return (this.length === 0)
    }
	// 返回链表包含的元素个数
    size() {
        return this.length
    }
	// 链表转换成字符串 value1,value2,value3
    toString() {
        let current = this.head;
        let str = '';
        while (current) {
            str += current.value + ((current.next ? ',': ''));
            current = current.next;
        }
        return str;
    }
}


双链表

原文链接：https://blog.csdn.net/qq_44810886/article/details/124540822

双向链表和单向链表的区别是双向链表比单向链表每个节点多一个头指针，这个指针指向前一个节点，每个节点包含包含头指针、数据域、尾指针， 因此从这个节点可以同时访问到它前面和后面的节点。

链表2

双链表的常见操作

  1. append(element) ：向列表尾部添加一个新的项

  2. insert(position,element): 向列表的特定位置插入一个新的项

  3. get(position): 获取对应位置的元素

  4. indexOf(element): 返回元素在列表中的索引。如果没有该元素返回-1

  5. updata(position,element) : 修改某个位置的元素

  6. removeAt(position)：从列表的特定位置移除某一项

  7. remove(element)：从列表中移除一项

  8. isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false

  9. size() ：返回链表包含的元素个数。与数组的length属性类似

  10. toString()： 由于列表使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值

  11. forwardString()：返回正向遍历的节点字符串形式

  12. backwardString()：返回反向遍历的节点字符串形式

双链表的函数式定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

 //封装双向链表
function DoublyLinkedList() {
    //内部类：节点类
    function Node(data) {
	this.data = data;
	this.prev = null;
	this.next = null;
    }
    //属性
    this.head = null;
    this.tail = null;
    this.length = 0;
}

//常见的操作封装
DoublyLinkedList.prototype.append = function(data) {
    //1.根据data创建节点
    var newNode = new Node(data)

    //2.判断添加的是否是第一个节点
    if (this.length == 0) {
        this.head = newNode
        this.tail = newNode
    } else {
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
    }
    this.length += 1
}

//将链表转换成字符串形式
//2.1 toString
DoublyLinkedList.prototype.toString = function() {
    return this.backwardString()

}
//2.2 forwardString方法
DoublyLinkedList.prototype.forwardString = function() {
    //1.定义变量
    var current = this.tail;
    var resultString = ""
    //2.依次向前遍历，获取每一个节点
    while (current) {
        resultString += current.data + " ";
        current = current.prev
    }
    return resultString

}

//2.3 backwardString方法
DoublyLinkedList.prototype.backwardString = function() {
    //1. 定义变量
    var current = this.head; //指向了第一个
    var resultString = "";
    //2.依次向后遍历，获取每一个节点
    while (current) { //只要current有值
        resultString += current.data + " ";
        current = current.next;
    }
    return resultString
}


//insert
DoublyLinkedList.prototype.insert = function(position, data) {
    //1. 越界判断
    if (position < 0 || position > this.length) return false
    //2.根据data创建新的节点
    var newNode = new Node(data)
    //3. 判断原来的列表是否为空
    if (this.length == 0) {
        this.head = newNode
        this.tail = newNode
    } else {
        if (position == 0) { //3.1 判断position是否为0
            this.head.prev = newNode; //原来的第一个节点的prev指向新插入的节点
            newNode.next = this.head; //指向原来的第一个节点
            this.head = newNode;
        } else if (position == this.length) { //插入到最后一个节点
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        } else { //插入到中间节点
            var current = this.head;
            var index = 0;
            while (index++ < position) {
                current = current.next;
            }
            //修改指针
            newNode.next = current;
            newNode.prev = current.prev;
            current.prev.next = newNode;
            current.prev = newNode;
        }
    }
    this.length += 1;
    return true
}

//get方法
DoublyLinkedList.prototype.get = function(position) {
    //1. 越界判断，注意后面有=
    if (position < 0 || position >= this.length) return null
    // 思路：this.length/2 >position  从头向后遍历
    // this.length/2 <position  从后向头遍历
    //2.获取元素
    var index = 0;
    var current = this.head;
    while (index++ < position) {
        current = current.next;
    }
    return current.data
}

//indexOf
DoublyLinkedList.prototype.indexOf = function(element) {
    var current = this.head;
    var index = 0;
    while (current) {
        if (current.data == element) {
            return index
        } else {
            current = current.next
            index += 1
        }
        return -1
    }
}

//updata方法
DoublyLinkedList.prototype.updata = function(position, newData) {
    //1. 越界判断，注意后面有=
    if (position < 0 || position >= this.length) return false
    var current = this.head;
    var index = 0;
    while (index++ < position) {
        current = current.next
    }
    current.data = newData
    return true
}

//removeAt
DoublyLinkedList.prototype.removeAt = function(position) {
    //1. 越界判断，注意后面有=
    if (position < 0 || position >= this.length) return null
    //2.判断是否只有一个节点
    var current = 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) {
            current = this.tail
            this.tail.prev.next = null;
            this.tail = this.tail.prev
        } else {
            var index = 0;

            while (index++ < position) {
                current = current.next;
            }
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }
    }
    //3. 
    this.length -= 1;
    return current.data
}


//remove方法
DoublyLinkedList.prototype.remove = function(data) {
    //1.根据data获取下标
    var index = this.indexOf(data)
    //2. 根据index删除对应位置的节点
    return this.removeAt(index)
}

//
DoublyLinkedList.prototype.isEmpty = function() {
    return this.length == 0
}

DoublyLinkedList.prototype.size = function() {
    return this.length
}

DoublyLinkedList.prototype.getHead = function() {
    return this.head.data
}

DoublyLinkedList.prototype.getTail = function() {
    return this.tail.data
}