单向链表

基本概念

在计算机科学中，链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，单向链表在每一个节点里存到下一个节点的指针(Pointer)。简单来说，单向链表可以用来储存数据，他在内存中不必是连续的内存空间，链表每个元素由元素本身的值和指向下一个元素的引用组成。

与数组比较

数组在通过下标获取元素或者是修改元素的性能比链表高，而链表在插入或者是删除元素的时候性能比数组高，因为数组在插入或者是删除的时候需要做大量的位移，他要给这个元素腾一个位置出来

常见方法

  1. append：向链表尾部添加一个新的元素
  2. insert：向链表的特定位置插入一个新的元素
  3. get：获取指定位置的元素
  4. indexOf：返回指定元素在链表中的索引，如果没找到该元素，就返回-1
  5. update：在链表修改指定位置的元素
  6. removeAt：在链表删除指定位置的元素
  7. remove：在链表删除指定元素
  8. isEmpty：如果链表中不包含任何元素返回true，否则返回false
  9. size：返回链表包含的元素个数
  10. toString：输出链表中元素的值

在js中实现链表

前置工作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//定义一个元素的类，
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

//定义一个链表类
class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
}

好，首先我们先定义一个类Node，因为链表中每一个元素都不是一个普通的值，而是一个对象，他需要包含当前位置元素的值和他下一个元素的引用，要指向下一个元素，在链表钟我们是通过这个引用一个个的往后面找的，一旦这个指针断了，那么后面的元素就找不到了，这一点在后面写代码的时候要时刻注意。

然后我们定义一个链表类，构造器中有一个head，他代表着当前链表的第一个元素，我们在插入和删除的时候都需要考虑到第一个元素的情况，他们的处理逻辑是不同的。然后是一个length，他代表这这个链表的长度。

注意下面所有方法都是定义在 LinkedList类中，为了简化代码，我就只写方法

实现append方法

实现插入方法也很简单，先看代码，再看分析

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
// 在链表末端插入方法
append(data) {
  const node = new Node(data);
  if (this.length === 0) {
    this.head = node;
  } else {
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = node;
  }
  t get(position) {
  // 1. 进行边缘判断
  if (position < 0 || position >= this.length) return null;

  // 2. 寻找对应的元素
  let index = 0;
  let current = this.head;
  while (index++ < position) {
    current = current.next;
  }
  return current.data;
}his.length++;
}

首先我们插入元素需要考虑到当前元素是不是链表的第一个元素，如果是，我们只需要将head指向这个元素实例化的对象即可

如果不是第一个元素，我们首先需要声明一个变量，然后判断这个变量的next属性，也就是有没有保存下一个元素的引用，如果没有就代表他是最后一个元素了，那个时候我们只需要将他的next指定我们根据传进来的元素(data)实例化的对象(node)即可。如果有我们就继续判断他下一个元素的next有没有保存指向下一个元素的引用。

实现insert方法

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
inster(position, data) {
  // 1. 做边缘判断：position为负数和大于当前链表长度的情况
  if (position < 0 || position > this.length) return false;

  // 2. 创建一个对象
  const node = new Node(data);

  // 3. 插入元素:需要考虑插入的元素是第一个的情况
  if (position == 0) {
    node.next = this.head;
    this.head = node;
  } else {
    let index = 0;
    // 当前元素
    let current = this.head;
    // 上一个元素
    let prive = null;
    while (index++ < position) {
      prive = current;
      current = current.next;
    }
    prive.next = node;
    node.next = current;
  }

  this.length++;
  return true;
}

在指定位置插入一个元素就麻烦一点，还记得上面讲过，我们不能随随便便将一个元素置为空，这会导致这条线断了，后面的元素全找不到了。所以我们在插入的时候拿到上一个元素和下一个元素，并且保存起来。

举个例子：有十个小朋友拉着手一字排开，然后来了个新的小朋友，他要排到这个队伍第五个位置，所以我们只需要让原本第五个人的左手拉着这个新来的小朋友的右手，然后这个新来的小朋友的左手拉着第四个小朋友的右手就可以了。如何用代码复现呢？

当找到该插入的位置的时候，我们将上一个位置的元素的next指向当前插入的元素，然后将当前插入的元素的next属性指向本该排在这个位置的元素就可以了。

插入之前

插入之后

实现get方法

1
2
3
4
5
6
7
8
9
10
11
12
13
// 拿到指定位置的元素
 get(position) {
   // 1. 进行边缘判断
   if (position < 0 || position >= this.length) return null;

   // 2. 寻找对应的元素
   let index = 0;
   let current = this.head;
   while (index++ < position) {
     current = current.next;
   }
   return current.data;
 }

get方法较为简单，就是根据index一直往后找，当index等于传入的position的时候就代表找到了，那么我们直接返回这个元素的值即可。同样的，我们也是定义一个current来保存当前元素，如果当前的位置不对，我就去找current的下一个元素就好了。

实现indexOf方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 返回指定元素的下标
indexOf(data) {
  let index = 0;
  let current = this.head;
  while (current) {
    if (current.data === data) {
      return index;
    } else {
      current = current.next;
      index++;
    }
  }
  return -1;
}

和get方法类似，判断当前current的data是不是等于传进来的data，如果是就代表找到了，那么我们就返回这个index出去，如果不是就继续找。最后没找到的话就返回-1就可

实现update方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 更新指定位置的元素
update(position, data) {
  // 判断位置小于0或者是位置大于长度，那就直接返回false，表示没找到
  if (position < 0 || position >= this.length) return false;

  //找到了就更新数据
  let index = 0;
  let current = this.head;
  while (index < position) {
    current = current.next;
    index++;
  }
  current.data = data;
  return true;
}

和前面的逻辑类似，只是在找到的时候将传进来的data赋值给current的data

实现removeAt方法

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
// 删除指定位置的元素
removeAt(position) {
  // 边缘判断
  if (position < 0 || position >= this.length) return false;

  // 删除指定元素
  // 判断是否删除的第一个节点
  let index = 0;
  let current = this.head;
  let prive = null;
  if (position === 0) {
    this.head = current.next;
    current = null;
  } else {
    while (index < position) {
      prive = current;
      current = current.next;
      index++;
    }
    prive.next = current.next;
    // 这里不置为null也不影响打印，但是都没用了，你还要留在哪来干什么，没必要
    current = null;
    this.length--;
    return true;
  }
}

删除元素也需要分情况，如果删除的是第一个元素，那么我们直接this.head指向原本的第二个元素就好，否则就按照逻辑继续删除即可，跟插入一样，需要先保存上一个元素和下一个元素。

删除元素有个点：如果不将删除的那个元素置为空，其实也不影响代码的执行。因为链接在查询的时候是按照next来一个个找的，我们已经没有next指向他了，但是我觉得既然没用了，何必保存着这个元素对象呢？当然因为没有人指向他，你也可以等待js的垃圾回收机制过来回收清除

实现remove方法

1
2
3
4
5
6
7
8
9
// 删除某一项
remove(data) {
  const index = this.indexOf(data);
  if (index !== -1) {
    this.removeAt(index);
    return true;
  }
  return false;
}

删除指定元素比较简单，如果我们之前的方法封装的好，我们只需要调用indexOf找到这个元素的下标，然后根据这个元素的下标调用removeAt方法即可

首先isEmpty方法

1
2
3
4
// 是否为空
isEmpty() {
  return this.length === 0 ? true : false;
}

我们在LinkedList类定义的length属性就派上用场了，我们只需要判断下长度登不等于0即可

实现size方法

1
2
3
4
// 返回链表长度
size() {
  return this.length;
}

直接将length属性返回出去即可