数组的缺点

  • 数组的创建通常需要申请一段连续的内存空间(一整块的内存)，并且大小是固定的(大多数编程语言数组都是固定的)，所以当当前数组不能满足容量需求时，需要扩容。 (一般情况下是申请一个更大的数组，比如 2 倍。 然后将原数组中的元素复制过去)
  • 而且在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移。
  • 尽管 JavaScript 的 Array 底层可以帮我们做这些事，但背后的原理依然是这样。

链表的优势

不同于数组，链表中的元素在内存中不必是连续的空间。

  • 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成。
  • 相对于数组，链表有一些优点：
    • 内存空间不是必须连续的。
    • 可以充分利用计算机的内存，实现灵活的内存动态管理。
    • 链表不必在创建时就确定大小，并且大小可以无限的延伸下去。
    • 链表在插入和删除数据时，时间复杂度可以达到 O(1)。 相对数组效率高很多。
  • 相对于数组，链表有一些缺点：
    • 链表访问任何一个位置的元素时，都需要从头开始访问。(无法跳过第一个元素访问任何一个元素)。
    • 无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素。

链表结构的封装

Node 类表示每个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
// class Node<T> {
//   val: T;
//   next: T | null = null;
//   constructor(val: T) {
//     this.val = val;
//   }
// }
class Node<T> {
  next: Node<T> | null = null;
  constructor(public val: T) {
    this.val = val;
  }
}

LinkedList 类表示链表

1
2
3
4
5
6
7
class LinkedList<T> {
  head: Node<T> | null = null;
  size: number = 0;
  get length() {
    return this.size;
  }
}

方法

append(value) 添加链表节点

traverse 遍历链表 返回 val 拼接字符串

insert(position,value) 指定位置插入节点

removeAt(position) 指定位置删除节点返回节点 val

get(position) 获取指定位置节点 val

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
// class Node<T> {
//   val: T;
//   next: T | null = null;
//   constructor(val: T) {
//     this.val = val;
//   }
// }
class Node<T> {
  next: Node<T> | null = null;
  constructor(public val: T) {
    this.val = val;
  }
}

class LinkedList<T> {
  head: Node<T> | null = null;
  size: number = 0;
  get length() {
    return this.size;
  }
  // 追加元素
  append(value: T): void {
    const node = new Node(value);
    if (!this.head) this.head = node;
    else {
      let current = this.head;
      while (current.next) current = current.next;
      current.next = node;
    }
    this.size++;
  }

  // 遍历
  traverse(): string {
    const value: T[] = [];
    let current = this.head;
    while (current) {
      value.push(current.val);
      current = current.next;
    }
    return value.join("->");
  }
  // 下标插入
  insert(position: number, value: T): boolean {
    // 判断越界
    if (position < 0 || position > this.size) return false;
    // 添加到第一个位置
    const newNode = new Node(value);
    let current = this.head;
    if (position === 0) {
      this.head = newNode;
      newNode.next = current;
    } else {
      //添加到其他位置
      let index = 0;
      let previous: Node<T> | null = null;
      while (index++ < position && current) {
        previous = current;
        current = current.next;
      }
      newNode.next = current;
      previous!.next = newNode;
    }
    this.size++;
    return true;
  }
  // 删除指定元素
  removeAt(position: number): T | null {
    // 越界
    if (position < 0 || position > this.size) return null;
    let current = this.head;
    // 删除head
    if (position === 0) this.head = current?.next ?? null;
    else {
      // 删除其他节点
      let index = 0;
      let previous: Node<T> | null = null;
      while (index++ < position && current) {
        previous = current;
        current = current.next;
      }
      previous!.next = current?.next ?? null;
    }
    this.size--;
    return current?.val ?? null;
  }
  get(position: number): T | null {
    if (position < 0 || position > this.size) return null;
    let index = 0;
    let current = this.head;
    while (index++ < position && current) current = current.next;
    return current?.val ?? null;
  }
}
const linkedList = new LinkedList<string>();
linkedList.append("aaa");
linkedList.append("bbb");
linkedList.append("ccc");
console.log(linkedList.traverse());
linkedList.insert(3, "ddd");
console.log(linkedList.traverse());
console.log(linkedList.removeAt(0));
console.log(linkedList.traverse());
console.log(linkedList.get(2));

export {};

问题：存在过多重复低吗

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
// class Node<T> {
//   val: T;
//   next: T | null = null;
//   constructor(val: T) {
//     this.val = val;
//   }
// }
class Node<T> {
  next: Node<T> | null = null;
  constructor(public val: T) {
    this.val = val;
  }
}

class LinkedList<T> {
  head: Node<T> | null = null;
  size: number = 0;
  get length() {
    return this.size;
  }
  // 根据下标获取节点
  private getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) current = current.next;
    return current;
  }
  // 追加元素
  append(value: T): void {
    const node = new Node(value);
    if (!this.head) this.head = node;
    else {
      let current = this.head;
      while (current.next) current = current.next;
      current.next = node;
    }
    this.size++;
  }

  // 遍历
  traverse(): string {
    const value: T[] = [];
    let current = this.head;
    while (current) {
      value.push(current.val);
      current = current.next;
    }
    return value.join("->");
  }
  // 下标插入
  insert(position: number, value: T): boolean {
    // 判断越界
    if (position < 0 || position > this.size) return false;
    // 添加到第一个位置
    const newNode = new Node(value);
    let current = this.head;
    if (position === 0) {
      this.head = newNode;
      newNode.next = current;
    } else {
      //添加到其他位置
      // let index = 0;
      // let previous: Node<T> | null = null;
      // while (index++ < position && current) {
      //   previous = current;
      //   current = current.next;
      // }
      // newNode.next = current;
      // previous!.next = newNode;
      const previous = this.getNode(position - 1);
      newNode.next = previous!.next;
      previous!.next = newNode;
    }
    this.size++;
    return true;
  }
  // 删除指定元素
  removeAt(position: number): T | null {
    // 越界
    if (position < 0 || position > this.size) return null;
    let current = this.head;
    let remove: Node<T> | null = null;
    // 删除head
    if (position === 0) this.head = current?.next ?? null;
    else {
      // 删除其他节点
      // let index = 0;
      // let previous: Node<T> | null = null;
      // while (index++ < position && current) {
      //   previous = current;
      //   current = current.next;
      // }
      // previous!.next = current?.next ?? null;
      const previous = this.getNode(position - 1);
      remove = previous!.next;
      previous!.next = previous?.next?.next ?? null;
    }
    this.size--;
    return remove?.val ?? null;
  }
  get(position: number): T | null {
    if (position < 0 || position > this.size) return null;
    return this.getNode(position)?.val ?? null;
  }
}
const linkedList = new LinkedList<string>();
linkedList.append("aaa");
linkedList.append("bbb");
linkedList.append("ccc");
console.log(linkedList.traverse());
linkedList.insert(3, "ddd");
console.log(linkedList.traverse());
console.log(linkedList.removeAt(1));
console.log(linkedList.traverse());
console.log(linkedList.get(2));

export {};

其他方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 更新指定位置节点
  update(position: number, value: T): void {
    if (position < 0 || position > this.size) return;
    this.getNode(position)!.val = value;
  }
  indexOf(value: T): number {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.val === value) return index;
      current = current.next;
      index++;
    }
    return -1;
  }
  // 删除指定value的节点
  remove(value: T): T | null {
    return this.removeAt(this.indexOf(value));
  }

定义接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import IList from "../types/IList"

interface ILinkedList<T> extends IList<T> {
  append(value: T): void
  traverse(): void
  insert(value: T, position: number): boolean
  removeAt(position: number): T | null
  get(positon: number): T | null
  update(value: T, position: number): boolean
  indexOf(value: T): number
  remove(value: T): T | null
}

export default ILinkedList

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
import ILinkedList from "./ILinkedList";
class Node<T> {
  next: Node<T> | null = null;
  constructor(public val: T) {
    this.val = val;
  }
}
class LinkedList<T> implements ILinkedList<T> {
  head: Node<T> | null = null;
  length: number = 0;
  get size() {
    return this.length;
  }
  // 根据下标获取节点
  private getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) current = current.next;
    return current;
  }
  // 追加元素
  append(value: T): void {
    const node = new Node(value);
    if (!this.head) this.head = node;
    else {
      let current = this.head;
      while (current.next) current = current.next;
      current.next = node;
    }
    this.length++;
  }
  // 遍历
  traverse(): string {
    const value: T[] = [];
    let current = this.head;
    while (current) {
      value.push(current.val);
      current = current.next;
    }
    return value.join("->");
  }
  peek() {
    return this.head?.val;
  }
  // 下标插入
  insert(value: T, position: number): boolean {
    // 判断越界
    if (position < 0 || position > this.size) return false;
    // 添加到第一个位置
    const newNode = new Node(value);
    let current = this.head;
    if (position === 0) {
      this.head = newNode;
      newNode.next = current;
    } else {
      const previous = this.getNode(position - 1);
      newNode.next = previous!.next;
      previous!.next = newNode;
    }
    this.length++;
    return true;
  }
  // 删除指定元素
  removeAt(position: number): T | null {
    // 越界
    if (position < 0 || position > this.size) return null;
    let current = this.head;
    let remove: Node<T> | null = null;
    // 删除head
    if (position === 0) this.head = current?.next ?? null;
    else {
      const previous = this.getNode(position - 1);
      remove = previous!.next;
      previous!.next = previous?.next?.next ?? null;
    }
    this.length--;
    return remove?.val ?? null;
  }
  get(position: number): T | null {
    if (position < 0 || position > this.size) return null;
    return this.getNode(position)?.val ?? null;
  }
  // 更新指定位置节点
  update(value: T, position: number): boolean {
    if (position < 0 || position > this.size) return false;
    this.getNode(position)!.val = value;
    return true;
  }
  indexOf(value: T): number {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.val === value) return index;
      current = current.next;
      index++;
    }
    return -1;
  }
  // 删除指定value的节点
  remove(value: T): T | null {
    return this.removeAt(this.indexOf(value));
  }
  isEmpty(): boolean {
    return this.length === 0;
  }
}
export {};

反转链表

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
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
// 非递归
function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head;
  let newHead: ListNode | null = null;
  while (head) {
    // 保存引用
    const current = head.next;
    // 每次循环改变节点指向为上一个节点
    head.next = newHead;
    // 为了下一次循环的第二步操作
    newHead = head;
    head = current;
  }
  return newHead;
}
// 递归
function reverseList1(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head;
  // 返回的就是最后一个节点 每次递归都会更新直到整个反转
  const newHead = reverseList1(head.next);
  head.next.next = null;
  head.next = head;
  return newHead;
}

删除链表中的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
function deleteNode(node: ListNode | null): void {
  node!.val = node!.next!.val;
  node!.next = node!.next!.next;
}
export {};