1. 前言 | 难凉热血

# 1. 前言

用 JS 实现一个简单的单向链表，并完成相关的功能。

# 2. 功能说明

push(value):从链表尾部添加一个新的节点
insertAfer(value,item):向链表中的 item 节点之后插入一个值为 value 的新节点
remove(value):删除链表中值为 value 的节点
removeAt(pos):删除链表中第 pos 个节点
find(value):查找链表中值为 value 的节点
findPrevious(value):查找链表中值为 value 的节点的前一个节点
indexof(vallue):查找链表中值为 value 的节点的索引值，如果查找不到则返回-1
size():获取当前链表的长度
getHead():获取当前链表的头节点
print():打印当前链表，供测试用

# 3. 代码实现

# 3.1 创建链表类

//创建一个Node辅助类，用来生成节点
function Node(value) {
  this.value = value;
  this.next = null;
}

//链表类
function LinkedList() {
  this.head = null;
  this.length = 0;
  //向链表尾部追加元素
  this.push = push;
  //从链表中查找某个元素
  this.find = find;
  //在链表中任意一个元素之后插入一个元素
  this.insertAfter = insertAfter;
  //从链表中查找任意元素节点的前一个节点
  this.findPrevious = findPrevious;
  //从链表中删除值为value的元素
  this.remove = remove;
  //返回当前链表的长度
  this.size = size;
  //查找某个元素在链表中的索引值
  this.indexof = indexof;
  //删除链表中第pos个元素
  this.removeAt = removeAt;
  //获取链表中第一个元素
  this.getHead = getHead;
  //打印当前的链表，供测试用
  this.print = print;
}

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

# 2.1 push(value):从链表尾部添加一个新的节点

function push(value) {
  var node = new Node(value);
  if (this.head == null) {
    this.head = node;
  } else {
    var current = this.head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = node;
  }
  length++;
}

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

# 3.3 insertAfer(value,item):向链表中的 item 节点之后插入一个值为 value 的新节点

function insertAfter(value, item) {
  var node = new Node(value);
  var current = this.find(item);
  if (current == null) {
    return console.log("找不到元素");
  }
  node.next = current.next;
  current.next = node;
  length++;
}

1
2
3
4
5
6
7
8
9
10

# 3.4 remove(value):删除链表中值为 value 的节点

function remove(value) {
  var current = this.find(value);
  if (!current) {
    return console.log("链表中找不到被删除的元素");
  }
  var previous = this.findPrevious(value);

  if (!previous) {
    this.head = current.next;
  } else {
    previous.next = current.next;
  }
  this.length--;
}

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

# 3.5 removeAt(pos):删除链表中第 pos 个节点

function removeAt(pos) {
  if (pos > -1 && pos < length) {
    var current = this.head;
    var index = 0;
    if (pos === 0) {
      this.head = current.next;
    } else {
      while (index < pos) {
        var previous = current;
        current = current.next;
        index++;
      }
      previous.next = current.next;
    }
    length--;
  } else {
    return null;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 3.6 find(value):查找链表中值为 value 的节点

function find(value) {
  var currentNode = this.head;
  if (currentNode == null) {
    console.log("这是一个空链表！！！");
    return null;
  }
  if (currentNode.value === value) {
    return currentNode;
  }
  while (currentNode.next) {
    currentNode = currentNode.next;
    if (currentNode.value === value) {
      return currentNode;
    }
  }
  console.log("没有找到该元素！！！");
  return null;
}

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

# 3.7 findPrevious(value):查找链表中值为 value 的节点的前一个节点

function findPrevious(value) {
  var current = this.head;
  if (current == null) {
    console.log("这是一个空链表");
    return null;
  }
  if (current.value === value) {
    console.log("当前查找的节点为链表的头节点，头节点前再无节点");
    return null;
  }
  while (current.next) {
    if (current.next.value === value) {
      return current;
    }
    current = current.next;
  }
  console.log("找不到该元素的前一个元素");
  return null;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 3.7 indexof(vallue):查找链表中值为 value 的节点的索引值，如果查找不到则返回-1

function indexof(value) {
  var current = this.head;
  var index = 0;
  if (current == null) {
    return null;
  } else {
    while (current) {
      if (current.value === value) {
        return index;
      }
      index++;
      current = current.next;
    }
  }
  return -1;
}

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

# 3.8 size():获取当前链表的长度

function size() {
  return length;
}

1
2
3

# 3.9 getHead():获取当前链表的头节点

function getHead() {
  return this.head;
}