发表更新Web前端12 分钟读完 (大约1869个字)

数据结构学习-链表

链表

链表是一种物理存储单元上非连续, 非顺序的存储结构, 数据元素的逻辑顺序是通过链表指针实现的, 链表由一些列结点组成, 每个节点包含两个部分: 一个是存储数据元素的数据域, 另一个是存储下一个结点地址的指针域

链表结构可以充分利用计算机内存空间, 实现灵活的内存动态管理, 但是链表失去了数组孙继读取的优点, 同时链表由于增加了结点的指针域, 空间开销比较大

链表的特点

  • 插入删除效率高 O(1), 只需要改变指针指向即可, 随机访问效率低 O(n)(需要从链头到链尾遍历)

  • 与数组相比, 内存空间消耗更大, 因为每个存储数据的节点都需要额外的空间存储后继指针

‍

‍

单链表

单链表的每一个节点, 都包含了数据区域和 next 指向下一个节点的指针

代码实现

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
class LinkNode {
    element: any;
    next: LinkNode | null | undefined;

    constructor(element: any) {
        this.element = element;
        this.next = null;
    }
}

class LinkedList {
    count: number;
    head: LinkNode | null | undefined;
    constructor() {
        this.count = 0;
        this.head = null;
    }
    push(element: any) {
        // 新建节点
        const newNode = new LinkNode(element);
        // 如果链表为空
        if (!this.head) {
            this.count++;
            this.head = newNode;
        } else {
            this.count++;
            let current = this.head;
            // 遍历链表, 直到最后一个元素
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        return newNode;
    }
    // 删除指定位置的节点
    removeAt(index: number) {
        let removeNode: LinkNode | null | undefined;
        if (index < 0 || index >= this.count || this.count === 0) {
            return undefined;
        } else {
            // 如果删除第一个元素
            if (index == 0) {
                // 头指针指向第二个元素
                removeNode = this.head;
                this.head = removeNode?.next;
                this.count--;
                console.log("要删除的元素是" + removeNode?.element);
                return removeNode?.element;
            } else {
                // 如果删除的不是第一个元素
                // 找到他的前一个元素
                const prev = this.getNodeAt(index - 1);
                removeNode = prev?.next;
                console.log("要删除的元素是" + removeNode?.element);
                // 要删除的元素前一个元素的next=要删除的元素后一个元素
                prev!.next = removeNode?.next;
                this.count--;
            }
            return removeNode?.element;
        }
    }
    remove(element: any) {
        const index = this.indexOf(element);

        if (index === -1) {
            return undefined;
        } else {
            return this.removeAt(index);
        }
    }
    indexOf(element: any) {
        // 根据数据, 返回索引
        let current = this.head;
        let index = 0;
        while (current?.next) {
            if (JSON.stringify(current.element) == JSON.stringify(element)) {
                return index;
            }
            index++;
            current = current?.next;
        }
        return -1;
    }

    getNodeAt(index: number) {
        let current = this.head;

        if (index < 0 || index >= this.count || this.count === 0) {
            return undefined;
        } else {
            for (let i = 0; i < index; i++) {
                current = current?.next;
            }
            return current;
        }
    }
    toString() {
        let current = this.head;
        let str = "";
        while (current) {
            str += JSON.stringify(current.element) + "-";
            current = current?.next;
        }
        return str;
    }
    insertElement(element: any, index: number) {
        if (index < 0 || index > this.count) {
            return undefined;
        }
        // 如果插入最后一个元素
        if (index === this.count) {
            return this.push(element);
        }
        const newNode = new LinkNode(element);
        // 如果在第一个元素之前插入
        if (index === 0) {
            this.count++;
            newNode.next = this.head;
            this.head = newNode;
            return this.head;
        }
        // 在指定位置插入一个元素
        // 新建一个节点, 新节点的next=插入位置的next, 插入位置的next=新节点,
        // 插入位置的节点
        const insertedNode = this.getNodeAt(index - 1);
        if (insertedNode) {
            this.count++;
            newNode.next = insertedNode?.next;
            insertedNode.next = newNode;
            return newNode;
        } else {
            return undefined;
        }
    }
    size() {
        return this.count;
    }
    isEmpty() {
        return this.size() === 0;
    }
}

‍

‍

单链表的应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 回文数检查
function check(str: string) {
    // 全部转小写, 去掉空格
    str = str.toLocaleLowerCase().split(" ").join("");
    console.log("处理后的字符串:" + str);
    // 将字符串加入队列
    const list = new LinkedList();
    for (let i = 0; i < str.length; i++) {
        list.push(str[i]);
    }
    let tag = true;

    // 取出首尾元素进行对比
    while (list.size() > 1) {
        if (list.removeAt(0) !== list.removeAt(list.size() - 1)) {
            tag = false;
            break;
        }
    }
    console.log(tag);
}

check("abc dc bA");

双向链表

节点除了数据区域外, 还有两个指针, 分别为前驱指针 prev 和后继指针 next

在双向链表中删除元素需要考虑以下边界条件：

  1. 如果链表为空，不能进行删除操作。

  2. 如果要删除的元素是头结点或者尾节点，则需要更新 head​ 或 tail​ 指针。

  3. 如果要删除的元素不是头节点或尾节点，则需要更新其前驱节点的 next​ 指针和后继节点的 prev​ 指针。

  4. 如果输入的索引超出链表长度，应该返回 undefined​。

特别地，如果链表只有一个元素，那么删除唯一一个元素后，需要将 head​ 和 tail​ 指针都置为 null​。

代码实现

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
import { LinkNode, LinkedList } from "./单链表";
class doubleLinkNode extends LinkNode {
    prev: doubleLinkNode | null | undefined;
    next: doubleLinkNode | null | undefined;
    constructor(element: any) {
        super(element);
        this.prev = null;
    }
}
class doubleLinkList extends LinkedList {
    head: doubleLinkNode | null | undefined;
    tail: doubleLinkNode | null | undefined;
    constructor() {
        super();
        this.tail = null;
    }
    push(element: any): doubleLinkNode {
        const node = new doubleLinkNode(element);
        // 如果链表内没有元素,
        // 直接添加
        if (this.head == null) {
            this.head = node;
            this.tail = node;
        } else {
            // 如果链表内有元素
            // 当前的最后一个元素的next指向新元素,
            // 新元素的prev指向当前的元素
            // 改变tail的指向
            this.tail!.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        this.count++;

        return node;
    }
    insert(element: any, index: number) {
        // 首先判断index是否符合条件
        if (index < 0 || index > this.count) {
            return undefined;
        }
        const node = new doubleLinkNode(element);

        if (index === 0) {
            // 如果没有元素
            if (!this.head) {
                this.head = node;
                this.tail = node;
            } else {
                // 如果有元素想要插入最前
                node.next = this.head;
                this.head.prev = node;
                this.head = node;
            }
        } else if (index === this.count) {
            // 如果是在最后插入
            this.tail!.next = node;
            node.prev = this.tail;
            this.tail = node;
        } else {
            // 在内部插入
            // 前一个结点的next=新节点
            // 后一个节点的prev=新节点
            // 新节点的prev=前一个结点
            // 新节点的next=后一个节点
            const prevNode = this.getNodeAt(index - 1) as doubleLinkNode;
            const nextNode = this.getNodeAt(index) as doubleLinkNode;

            prevNode.next = node;
            nextNode.prev = node;
            node.prev = prevNode;
            node.next = nextNode;
        }

        this.count++;
        return node;
    }

    removeAt(index: number) {
        //在双向链表中删除元素需要考虑以下边界条件：
        // 如果链表为空，不能进行删除操作。
        // 如果要删除的元素是头结点或者尾节点，则需要更新 head 或 tail 指针。
        // 如果要删除的元素不是头节点或尾节点，则需要更新其前驱节点的 next 指针和后继节点的 prev 指针。
        // 如果输入的索引超出链表长度，应该返回 undefined。
        // 特别地，如果链表只有一个元素，那么删除唯一一个元素后，需要将 head 和 tail 指针都置为 null。
        if (index < 0 || index >= this.count || this.count == 0) {
            return undefined;
        }
        let current: doubleLinkNode | null | undefined;
        if (index === 0) {
            current = this.head;
            if (this.count === 1) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = current?.next;
                this.head!.prev = null;
            }
        } else if (index === this.count - 1) {
            // 删除最后的元素
            current = this.tail;
            this.tail = current?.prev;
            this.tail!.next = null;
        } else {
            // 删除中间的元素
            const prevNode = this.getNodeAt(index - 1) as doubleLinkNode;
            current = prevNode.next;
            prevNode.next = current?.next;
            current!.next!.prev = prevNode;
        }
        this.count--;
        return current;
    }
}

‍

循环链表

循环列表的最后一个结点的 next 指向 head 结点

代码实现

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
import { LinkNode, LinkedList } from "./单链表";

class circularLinkedList extends LinkedList {
    constructor() {
        super();
    }
    push(element: any): LinkNode {
        const newNode = new LinkNode(element);

        // 如果空表
        if (this.count === 0) {
            this.head = newNode;
        } else {
            const current = this.getNodeAt(this.count - 1);
            current!.next = newNode;
        }

        newNode.next = this.head;
        this.count++;
        return newNode;
    }
    insertElement(element: any, index: number): LinkNode | undefined {
        if (index < 0 || index > this.count) {
            return;
        }
        const newNode = new LinkNode(element);
        let current = this.head;
        if (index === 0) {
            // 如果没有元素
            if (this.count === 0) {
                this.head = newNode;
                newNode.next = this.head;
            } else {
                newNode.next = current;
                this.head = newNode;

                // 将最后的元素重新指向头
                current = this.getNodeAt(this.count - 1);
                current!.next = this.head;
            }
        } else {
            // 在中间插入
            current = this.getNodeAt(index - 1);
            newNode.next = current?.next;
            current!.next = newNode;
        }
        this.count++;
        return newNode;
    }

    removeAt(index: number) {
        if (index < 0 || index >= this.count || this.count === 0) {
            return;
        }
        let current = this.head;
        if (index === 0) {
            if (this.count === 1) {
                // 如果只有一个元素
                this.head = null;
            } else {
                let last = this.getNodeAt(this.count - 1);
                this.head = current?.next;
                last!.next = this.head;
            }
        } else {
            current = this.getNodeAt(index - 1);
            current!.next = current?.next?.next;
        }
        this.count--;
        return current;
    }
}

‍

数据结构学习-链表

https://cuijunyu.win/20230308/数据结构学习-链表/

作者

cuicui

发布于

2023-03-08

更新于

2023-04-23

许可协议

#

评论

关注我

链接

分类

最新文章

归档

标签

CSS1
Chrome1
CloudFlare1
ES61
Flex1
JavaScript7
Mipush1
Promise1
TypeScript1
WebSocket1
css1
git1
javaScript1
kali1
nginx1
ocr3
openai1
pandoc1
pwa1
snipaste4
test1
typeScript2
vue5
vue-router1
word1
小工具1
数据结构5
面试1
×