mahaaoo
0%

js单链表实现

Posted on Edited on In

定义

​ 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

与数组的区别

​ 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

链表的设计

节点

链表的基本存储结构就是一个个的节点，首先先创建一个节点

1
2
3
4
5
6
7
8
9
// 链表节点
function LinkedNode(node) {
    this.val = node;
    this.next = null;
}

// val表示该节点上存储的值
// next表示该节点的下一个节点
// 一般的单向链表的尾节点指向null

链表

一般链表的第一个节点为head，用来表示这是一个链表存储，在创建链表的时候我们为链表的第一个节点默认设置为head

1
2
3
4
// 链表
function LinkedList() {
    this.head = new LinkedNode('head');     //头节点
}

这样我们就实现了一个最简单的链表。仿照数组的操作，之后我们为链表添加上基本的增删改查功能。

长度

为了方便链表操作，首先要记录一下链表的长度。在操作链表的时候记得相应的增减。

1
2
3
4
function LinkedList() {
    this.head = new LinkedNode('head');     //头节点
+    this.length = 0; // 链表默认的长度为0
}

显示链表

在操作链表之前，先能看到链表的样子，方便后续的测试。只需要遍历一下链表，按照自己喜欢的格式打印出链表即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function LinkedList() {
    this.head = new LinkedNode('head');     //头节点
    this.length = 0;
+    this.display = display;             //显示链表
}

// 显示链表
function display() {
    let currNode = this.head;
    let linkString = '';
    while (currNode != null){
        linkString = linkString + currNode.val + '->';
        currNode = currNode.next;
    }
    console.log(linkString + 'tail');
}

ok～现在已经得到了一个链表了，现在测试一下这个链表

1
2
3
let testLink = new LinkedList();
testLink.display();  // 打印这个链表
console.log('链表长度为：' + testLink.length);

head->tail
链表长度为：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
function LinkedList() {
    this.head = new LinkedNode('head');     //头节点
    this.display = display;             //显示链表
    this.length = 0;
+    this.add = add; // 添加节点
}

// 向链表添加一个元素
function add(item) {
    let currNode = this.head;
    while(currNode.next != null) {
        currNode = currNode.next;
    }
    currNode.next = new LinkedNode(item);
    this.length ++; // 链表变长了1
}


// 测试
let testLink = new LinkedList();
// 链表添加元素
testLink.add('first');
testLink.add('apple');
testLink.add('ball');

testLink.display();
console.log('链表长度为：' + testLink.length);

head->first->apple->ball->tail
链表长度为：3

查找指定节点

查找指定节点所在链表中的位置

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
function LinkedList() {
    this.head = new LinkedNode('head');     //头节点
    this.add = add;
    this.display = display;             //显示链表
    this.length = 0;
    
+    this.find = find;                   //查找节点
}

function find(item) {
    let currNode = this.head;
    let index = 0;
    while (currNode.val != item){
        if(currNode.next == null) {
            console.log("该链表中不存在这个节点")
            return currNode;
        }
        currNode = currNode.next;
        index++;
    }
    console.log(`${item}是该链表的第${index}个节点`);
    return currNode;
}

// 测试
let testLink = new LinkedList();
// 链表添加元素
testLink.add('first');
testLink.add('apple');
testLink.add('ball');

// // 查找链表
testLink.find('apple');
testLink.find('second');

apple是该链表的第2个节点
该链表中不存在这个节点

向指定节点后添加一个节点

首先先要找到指定的节点，若没有查找这个节点则插入失败

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
function LinkedList() {
    this.head = new LinkedNode('head');     //头节点
    this.find = find;                   //查找节点
    this.add = add;
    this.display = display;             //显示链表
    this.length = 0;
    
+    this.insert = insert;               //插入节点
}

function insert (newElement, item) {
    var newNode = new LinkedNode(newElement);
    var currNode = this.find(item);
    if(currNode.next == null) {
        console.log("插入失败：不存在该节点");
        return null;
    };
    newNode.next = currNode.next;
    currNode.next = newNode;
    console.log("插入成功");
}

// 测试

let testLink = new LinkedList();
// 链表添加元素
testLink.add('first');
testLink.add('apple');
testLink.add('ball');

testLink.insert('second', 'first');
testLink.insert('second', 'ccc');

插入成功
该链表中不存在这个节点
插入失败：不存在该节点

删除指定节点

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
function LinkedList() {
    this.head = new LinkedNode('head');     //头节点
    this.find = find;                   //查找节点
    this.add = add;
    this.insert = insert;               //插入节点
    this.display = display;             //显示链表
    this.length = 0;
    
+    this.remove = remove;               //删除节点
}

function remove(item) {
    let currNode = this.head;
    while(currNode.next != null) {
        if(currNode.next.val == item) {
            currNode.next = currNode.next.next;
            break;
        }
        currNode = currNode.next
    }
    this.length --; // 链表变短了
}

// 测试
let testLink = new LinkedList();
// 链表添加元素
testLink.add('first');
testLink.add('apple');
testLink.add('ball');

testLink.display();
console.log('链表长度为：' + testLink.length);

// 删除一个节点
testLink.remove('apple');
testLink.display();
console.log('链表长度为：' + testLink.length);

head->first->apple->ball->tail
链表长度为：3
head->first->ball->tail
链表长度为：2

全部代码

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
// 链表node节点
function LinkedNode(node) {
    this.val = node;
    this.next = null;
}

function LinkedList() {
    this.head = new LinkedNode('head');     //头节点
    this.find = find;                   //查找节点
    this.add = add;
    this.insert = insert;               //插入节点
    this.remove = remove;               //删除节点
    this.display = display;             //显示链表
    this.length = 0;
}

// 向链表添加一个元素
function add(item) {
    let currNode = this.head;
    while(currNode.next != null) {
        currNode = currNode.next;
    }
    currNode.next = new LinkedNode(item);
    this.length ++;
}

//查找给定节点
function find(item) {
    let currNode = this.head;
    let index = 0;
    while (currNode.val != item){
        if(currNode.next == null) {
            console.log("该链表中不存在这个节点")
            return currNode;
        }
        currNode = currNode.next;
        index++;
    }
    console.log(`${item}是该链表的第${index}个节点`);
    return currNode;
}

// 显示链表
function display() {
    let currNode = this.head;
    let linkString = '';
    while (currNode != null){
        linkString = linkString + currNode.val + '->';
        currNode = currNode.next;
    }
    console.log(linkString + 'tail');
}

function insert (newElement, item) {
    var newNode = new LinkedNode(newElement);
    var currNode = this.find(item);
    if(currNode.next == null) {
        console.log("插入失败：不存在该节点");
        return null;
    };
    newNode.next = currNode.next;
    currNode.next = newNode;
    console.log("插入成功");
}

function remove(item) {
    let currNode = this.head;
    while(currNode.next != null) {
        if(currNode.next.val == item) {
            currNode.next = currNode.next.next;
            break;
        }
        currNode = currNode.next
    }
    this.length--;
}

let testLink = new LinkedList();
// 链表添加元素
testLink.add('first');
testLink.add('apple');
testLink.add('ball');

// 查找链表
testLink.find('apple');
testLink.find('second');

// 插入
testLink.insert('second', 'first');
testLink.insert('second', 'ccc');

// 删除
testLink.remove('apple');

testLink.display();
console.log('链表长度为：' + testLink.length);

参考资料