# 链表

链表是物理存储单元上非连续、非顺序的存储结构，有一系列节点组成。

# 单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。

节点

节点包含两个部分，一部分是存储数据元素的数据域，一部分是存储指向下一个节点的指针域，上图中绿色的部分就是数据域，蓝色的部分是指针域，他们一起共同构成一个节点。一个节点可以用如下方式定义和使用。

var Node = function(data) {
  this.data = data;
  this.next = null;
}

var node1 = new Node(1);
var node2 = new Node(2);
var node3 = new Node(3;

node1.next = node2;
node2.next = node3;

1
2
3
4
5
6
7
8
9
10
11

首位节点

链表中的第一个节点是首节点，最后一个节点是尾节点。

有头链表和无头链表

无头链表是指第一个节点既有数据域，又有指针域，第一个节点既是首节点又是头结点。有头链表是指第一个节点只有指针域，而没有数据域。在链表定义中展示的就是无头链表，一个有头链表的结构图如下

# 单链表的实现

function LinkList() {
  var Node = function(data) {
    // 定义节点
    this.data = data;
    this.next = null;
  };

  var length = 0; // 长度
  var head = null; // 头结点
  var tail = null; // 尾节点
}

1
2
3
4
5
6
7
8
9
10
11

# 链表的方法

append(data), 添加一个新的元素
insert(index, data), 在指定位置插入一个元素
remove(index), 删除指定位置的节点
removeHead(), 删除首节点
removeTail(), 删除尾节点
indexOf(data), 返回指定元素的索引
get(index), 返回指定索引位置的元素
head(), 返回尾节点
tail(), 返回尾节点
isEmpty(), 判断链表是否为空
clear(), 清空链表
print(), 打印整个链表
length(), 返回链表的长度

# append 方法

每次 append，都要先创建一个节点，如果列表为空，则让 head 和 tail 指向整个新创建的节点。
如果不为空，则 tail.next = node, 并让 tail 指向 node

this.append = function(data) {
  var node = new Node(data);

  if (head == null) {
    head = node;
    tail = head;
  } else {
    tail.next = node;
    tail = node;
  }
  length += 1;
  return true;
};

1
2
3
4
5
6
7
8
9
10
11
12
13

# print 方法

print 方法纯粹为了验证链表其他方法是否正确而存在，目的是输出链表。

this.print = function() {
  var currNode = head;
  var strLink = "";
  while (currNode) {
    strLink += currNode.data.toString() + " ->";
    currNode = currNode.next;
  }
  strLink += "null";
  console.log(strLink);
};

1
2
3
4
5
6
7
8
9
10

# insert 方法

append 只能在链表的末尾添加元素，而 insert 可以在指定位置插入一个元素，新增数据的方式更加灵活，insert 方法需要传入参数 index，指明要插入的索引位置。该方法的关键是找到索引为 index - 1 的节点，只有找到这个节点，才能将新的节点插入到链表中。和索引相关的方法，先要考虑索引的范围是否合法，然后考虑索引的边界情况。

如果 index == length, 那么可以直接用 append 方法
如果 index > length 或者 index < 0, 索引错误，返回 null
如果 index == 0, 创建新节点 newNode, 这个新的节点索引是 0，因此是链表的首节点，让 newNode.next = head, head = newNode
如果 index > 0 且 index < length, 同样创建新节点 newNode, 变量 currNode 指向 head, insertIndex = 1, 表示 newNode 应该插入的位置，使用 while 循环，循环条件是 insertIndex < index, 在循环体内，insertIndex 加 1，currNode = currNode.next, 这样当循环结束的时候，currNode 就是 newNode 的上一个节点，让 newNode 指向 currNode 的下一个节点，而 currNode 指向 newNode。

this.insert = function(index, data) {
  if (index === length) {
    return this.append(data);
  } else if (index > length || index < 0) {
    return false;
  } else {
    if (index === 0) {
      var newNode = new Node(data);
      head = newNode;
    } else {
      var insertIndex = 1;
      var currNode = head;
      // 找到应该插入的位置
      while (insertIndex < index) {
        currNode = currNode.next;
        insertIndex += 1;
      }
      var nextNode = currNode.next;
      currNode.next = newNode;
      newNode.next = nextNode;
    }
    length += 1;
    return true;
  }
};

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

# remove 方法

删除指定位置的节点，需要传入参数 index，和 insert 方法一样，先考虑索引的范围是否合法，然后考虑索引在边界时的操作，关键点是找到索引为 index-1 的这个节点，这个节点的 next 指向了要删除的节点。

如果 index 小于 0 或者大于等于 length，索引是错误的，返回 null
如果 index 等于 0，删除的是首节点，执行 delNode=head,head=head.next,然后返回 delNode
如果 index>0 且小于 length,使用一个 while 循环，找到需要被删除的位置，delNode 表示被删除的节点，while 的结束条件是 delIndex < index,在循环体内，delIndex 加 1，preNode 指向 currNode, currNode 指向自己的下一个节点。当循环结束时，delNode=currNode, preNode.next=currNode.next,这样就把 currNode 从链表中删除了，需要特殊处理的是尾节点，tail 要指向 preNode,因为 preNode 成了新的尾节点。

// 删除指定位置的节点
this.remove = function(index) {
  if (index < 0 || index >= length) {
    return null;
  } else {
    var delNode = null;
    if (index == 0) {
      // head指向下一个节点
      delNode = head;
      head = head.next;
    } else {
      var delIndex = 0;
      var preNode = null;
      var currNode = head;
      while (delIndex < index) {
        delIndex += 1;
        preNode = currNode;
        currNode = currNode.next;
      }
      delNode = currNode;
      preNode.next = currNode.next;
      // 如果删除的是尾节点
      if (currNode.next == null) {
        tail = preNode;
      }
    }
    length -= 1;
    delNode.next = null;
    return delNode.data;
  }
};

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

# get 方法

如果 index 小于 0 或者大于等于 length，索引是错误的，返回 null
如果 index>0 且小于 length,使用一个 while 循环，循环条件是 nodeIndex < index, 循环体内，nodeIndex 加 1，currNode 指向下一个节点，循环结束后，currNode 就是索引为 index 的节点

this.get = function(index) {
  if (index < 0 || index >= length) {
    return null;
  }
  var nodeIndex = 0;
  var currNode = head;
  while (nodeIndex < index) {
    nodeIndex += 1;
    currNode = currNode.next;
  }
  return currNode.data;
};

1
2
3
4
5
6
7
8
9
10
11
12

# indexOf 方法

// 返回指定元素的索引,如果没有,返回-1
// 有多个相同元素,返回第一个
this.indexOf = function(data) {
  var index = -1;
  var currNode = head;
  while (currNode) {
    index += 1;
    if (currNode.data == data) {
      return index;
    } else {
      currNode = currNode.next;
    }
  }
  return -1;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 完整代码

function LinkList() {
  // 定义节点
  var Node = function(data) {
    this.data = data;
    this.next = null;
  };

  var length = 0; // 长度
  var head = null; // 头节点
  var tail = null; // 尾节点

  // 添加一个新元素
  this.append = function(data) {
    // 创建新节点
    var node = new Node(data);
    // 如果是空链表
    if (head == null) {
      head = node;
      tail = head;
    } else {
      tail.next = node; // 尾节点指向新创建的节点
      tail = node; // tail指向链表的最后一个节点
    }
    length += 1; // 长度加1
    return true;
  };

  // 返回链表大小
  this.length = function() {
    return length;
  };

  // 在指定位置插入新的元素
  this.insert = function(index, data) {
    if (index == length) {
      return this.append(data);
    } else if (index > length || index < 0) {
      return false;
    } else {
      var newNode = new Node(data);
      if (index == 0) {
        newNode.next = head;
        head = newNode;
      } else {
        var insertIndex = 1;
        var currNode = head;
        // 找到应该插入的位置
        while (insertIndex < index) {
          currNode = currNode.next;
          insertIndex += 1;
        }
        var next_node = currNode.next;
        currNode.next = newNode;
        newNode.next = next_node;
      }
      length += 1;
      return true;
    }
  };

  // 删除指定位置的节点
  this.remove = function(index) {
    if (index < 0 || index >= length) {
      return null;
    } else {
      var delNode = null;
      if (index == 0) {
        // head指向下一个节点
        delNode = head;
        head = head.next;
      } else {
        var delIndex = 0;
        var preNode = null;
        var currNode = head;
        while (delIndex < index) {
          delIndex += 1;
          preNode = currNode;
          currNode = currNode.next;
        }
        delNode = currNode;
        preNode.next = currNode.next;
        // 如果删除的是尾节点
        if (currNode.next == null) {
          tail = preNode;
        }
      }
      length -= 1;
      delNode.next = null;
      return delNode.data;
    }
  };

  // 删除尾节点
  this.removeTail = function() {
    return this.remove(length - 1);
  };

  // 删除头节点
  this.removeHead = function() {
    return this.remove(0);
  };

  // 返回指定位置节点的值
  this.get = function(index) {
    if (index < 0 || index >= length) {
      return null;
    }

    var nodeIndex = 0;
    var currNode = head;
    while (nodeIndex < index) {
      nodeIndex += 1;
      currNode = currNode.next;
    }
    return currNode.data;
  };

  // 返回链表头节点的值
  this.head = function() {
    return this.get(0);
  };

  // 返回链表尾节点的值
  this.tail = function() {
    return this.get(length - 1);
  };

  // 返回指定元素的索引,如果没有,返回-1
  // 有多个相同元素,返回第一个
  this.indexOf = function(data) {
    var index = -1;
    var currNode = head;
    while (currNode) {
      index += 1;
      if (currNode.data == data) {
        return index;
      } else {
        currNode = currNode.next;
      }
    }
    return -1;
  };

  // 输出链表
  this.print = function() {
    var currNode = head;
    var strLink = "";
    while (currNode) {
      strLink += currNode.data.toString() + "->";
      currNode = currNode.next;
    }
    strLink += "null";
    console.log(strLink);
    console.log("length:" + length);
  };

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

  // 清空链表
  this.clear = function() {
    head = null;
    tail = null;
    length = 0;
  };
}

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

# 基于链表实现栈和队列

链表实现栈

function Stack() {
  var linklist = new LinkList();

  // 从栈顶添加元素
  this.push = function(item) {
    linklist.append(item);
  };

  // 弹出栈顶元素
  this.pop = function() {
    return linklist.removeTail();
  };

  // 返回栈顶元素
  this.top = function() {
    return linklist.tail();
  };

  // 返回栈的大小
  this.size = function() {
    return linklist.length();
  };

  // 判断是否为空
  this.isEmpty = function() {
    return linklist.isEmpty();
  };

  // 清空栈
  this.clear = function() {
    linklist.clear();
  };
}

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

链表实现队列

function Queue() {
  var linklist = new LinkList();

  // 入队列
  this.enqueue = function(item) {
    linklist.append(item);
  };

  // 出队列
  this.dequeue = function() {
    return linklist.removeHead();
  };

  // 返回队首
  this.head = function() {
    return linklist.head();
  };

  // 返回队尾
  this.tail = function() {
    return linklist.tail();
  };

  // size
  this.size = function() {
    return linklist.length();
  };

  //clear
  this.clear = function() {
    linklist.clear();
  };

  // isEmpty
  this.isEmpty = function() {
    return linklist.isEmpty();
  };
}

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

# 反转一个单链表

一种解决方案是按原始顺序迭代结点，并将它们逐个移动到列表的头部。似乎很难理解。我们先用一个例子来说明我们的算法。

23 -> 6 -> 15 -> null

首先，我们将黑色结点的下一个结点（即结点 6）移动到列表的头部：
然后，我们将黑色结点的下一个结点（即结点 15）移动到列表的头部：
黑色结点的下一个结点现在是空。因此，我们停止这一过程并返回新的头结点 15。

在该算法中，每个结点只移动一次。

因此，时间复杂度为 O(N)，其中 N 是链表的长度。我们只使用常量级的额外空间，所以空间复杂度为 O(1)。

这个问题是你在面试中可能遇到的许多链表问题的基础。

function reverseList(head) {
  if (!head) {
    return null;
  }
  var currNode = head; // 当前要翻转的节点
  var preNode = null; // 前一个节点
  while (currNode) {
    var nextNode = currNode.next; // 下一个节点
    currNode.next = preNode; // 对当前节点进行翻转
    preNode = currNode;
    currNode = nextNode;
  }
  //最后要返回preNode,当循环结束时,preNode指向翻转前链表的最后一个节点
  return preNode;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

← 队列哈希表 →