数据结构-链表

发表于 | 分类于 |

chapter-6 链表

数组的缺点

  • 很多语言里，数组的长度固定。填满后，加入新元素很困难。
  • 添加、删除元素也很麻烦，因为需要将数组中其他元素向前或向后平移，以反映刚刚进行了添加或删除操作。
  • JavaScript数组不存在上述问题，split方法不需要再访问数组中其他元素了，主要问题是：它们被实现成了对象，与其他语言相比，效率很低。
  • 如果数组使用中很慢，可以考虑用链表代替它，除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况。需要随机访问，数组是更好的选择。

定义链表

  • 一组节点组成的集合。
  • 每个节点使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。
  • 数组靠位置进行引用，链表靠相互之间的关系进行引用。
  • 遍历链表是跟着链接，从首元素走到尾元素（不包含头节点，作为链表的接入点），尾元素指向一个null节点。
  • 头节点是一个特殊固定节点。
  • 插入一个节点的效率很高，修改它前面的节点（前驱），使其指向新加入的节点，新加入的节点则指向原来前驱指向的节点。
  • 删除一个节点，将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向null

设计一个基于对象的链表

  • 包含两个类：Node类用来表示节点，LinkedList类提供插入、删除、显示列表元素、及一些辅助方法。
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
// 节点类
function Node (element) {
    // 保存节点上的数据
    this.element = element;
    // 保存指向下一个节点的链接
    this.next = null; 
}
// 提供对链表进行操作的方法
function LList () {
    // 属性：使用一个Node对象保存该链表的头节点
    this.head = new Node('head');
}
LList.prototype = {
    constructor: LList,
    // 查找给定的节点
    find: function (item) {
        var currNode = this.head;
        while (currNode.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 查找给定的节点前面的节点
    findPrevious (item) {
        var currNode = this.head;
        while (currNode.next !== null && currNode.next.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 指定节点后插入节点
    insert: function (newElement, item) {
        // 创建新节点
        var newNode = new Node(newElement);
        // 查找需要插入的位置
        var current = this.find(item);
        // 新节点指向current的下一个节点
        newNode.next = current.next;
        // current节点的下一个节点指向新节点
        current.next = newNode;
    },
    // 删除节点
    remove: function (item) {
        // 找到待删除节点前面的节点
        var prevNode = this.findPrevious(item);
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next;
        }
    },
    // 显示列表中元素
    display: function () {
        // 从头节点开始循环，不显示头节点
        var currNode = this.head;
        while (currNode.next !== null) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    }
}
// 主程序
var cities = new LList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('Carlisle', 'Russellville');
cities.insert('Alma', 'Carlisle');
console.log('链表整体数据：============');
cities.display();
cities.remove('Russellville');
console.log('删除数据Russellville后数据：============');
cities.display();
1.jpeg

双向链表

  • 从链表的头节点遍历到尾节点很简单，但是反过来，从后向前遍历则没那么简单。给Node增加一个属性，存储指向前驱节点的链接。
  • 插入时，需要更多的工作，指出节点正确的前驱和后继。
  • 删除时，效率提高了，不需要再查找待删除节点的前驱节点了。
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
/**
 * 双向链表实现
 */
// 节点类
function Node (element) {
    // 保存节点上的数据
    this.element = element;
    // 保存指向下一个节点的链接
    this.next = null; 
    // 保存前驱节点指向
    this.previous = null;
}
// 提供对链表进行操作的方法
function LList () {
    // 属性：使用一个Node对象保存该链表的头节点
    this.head = new Node('head');
}
LList.prototype = {
    constructor: LList,
    // 查找给定的节点
    find: function (item) {
        var currNode = this.head;
        while (currNode.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 查找最后的节点
    findLast () {
        var currNode = this.head;
        while (currNode.next !== null) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 指定节点后插入节点
    insert: function (newElement, item) {
        // 创建新节点
        var newNode = new Node(newElement);
        // 查找需要插入的位置
        var current = this.find(item);
        // 新节点指向current的下一个节点
        newNode.next = current.next;
        // 新节点的前驱属性
        newNode.previous = current;
        // current节点的下一个节点指向新节点
        current.next = newNode;
    },
    // 删除节点
    remove: function (item) {
        var currNode = this.find(item);
        if (currNode.next !== null) {
            currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
            currNode.next = null;
            currNode.previous = null;
        }
    },
    // 显示列表中元素
    display: function () {
        // 从头节点开始循环，不显示头节点
        var currNode = this.head;
        while (currNode.next !== null) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    },
    // 反序显示双向链表中的元素
    dispReverse: function () {
        var currNode = this.head;
        currNode = this.findLast();
        while (currNode.previous !== null) {
            console.log(currNode.element);
            currNode = currNode.previous;
        }
    }
}
// 主程序
var cities = new LList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('Carlisle', 'Russellville');
cities.insert('Alma', 'Carlisle');
console.log('链表整体数据：============');
cities.display();
cities.remove('Russellville');
console.log('删除数据Russellville后数据：============');
cities.display();
console.log('反转展示数据：============');
cities.dispReverse();

计算了一下时间：

  • 插入10000个Node的时间
    • 普通链表和双向链表差不多，普通链表240ms，双向链表250ms
  • 依次删除这全部10000个节点
    • 普通链表在150ms左右
    • 双向链表时间则较长，需要230ms左右
  • 随机删除一个元素（Math.random()）
    • 普通链表平均：0.283ms
    • 双向链表平均：0.196ms

所以书上写的双向链表更高效应该是指随机删除任意一个元素的平均时间

循环链表

  • 节点类型和单向链表类似，区别是，创建循环链表时，让其头节点的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
/**
 * 循环链表实现
 */
// 节点类
function Node (element) {
    // 保存节点上的数据
    this.element = element;
    // 保存指向下一个节点的链接
    this.next = null; 
}
// 提供对链表进行操作的方法
function LList () {
    // 属性：使用一个Node对象保存该链表的头节点
    this.head = new Node('head');
    this.head.next = this.head;
}
LList.prototype = {
    constructor: LList,
    // 查找给定的节点
    find: function (item) {
        var currNode = this.head;
        while (currNode.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 查找给定的节点前面的节点
    findPrevious (item) {
        var currNode = this.head;
        while (currNode.next !== null && currNode.next.element !== 'head' && currNode.next.element !== item) {
            currNode = currNode.next;
        }
        return currNode;
    },
    // 指定节点后插入节点
    insert: function (newElement, item) {
        // 创建新节点
        var newNode = new Node(newElement);
        // 查找需要插入的位置
        var current = this.find(item);
        // 新节点指向current的下一个节点
        newNode.next = current.next;
        // current节点的下一个节点指向新节点
        current.next = newNode;
    },
    // 删除节点
    remove: function (item) {
        // 找到待删除节点前面的节点
        var prevNode = this.findPrevious(item);
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next;
        }
    },
    // 显示列表中元素
    display: function () {
        // 从头节点开始循环，不显示头节点
        var currNode = this.head;
        // 检查头节点
        while (currNode.next !== null && currNode.next.element !== 'head') {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    },
    // 反序显示循环链表中的元素
    dispReverse: function () {
        var currNode = this.head;
        var prevNode = this.findPrevious(currNode.element);
        while (prevNode.element !== currNode.element && prevNode.element !== 'head') {
            console.log(prevNode.element);
            currNode = prevNode;
            prevNode = this.findPrevious(currNode.element);
        }
    }
}
var cities = new LList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('Carlisle', 'Russellville');
cities.insert('Alma', 'Carlisle');
console.log('链表整体数据：============');
cities.display();
cities.remove('Russellville');
console.log('删除数据Russellville后数据：============');
cities.display();
// debugger
console.log('反转展示数据：============');
console.time();
cities.dispReverse();
console.timeEnd();// 1.213ms

一般正常情况所说的链表都是双向链表，比较快