数据结构4-链表

数据结构 Comments

链表优缺点

对于数组来说，链表的优缺点：

数组的缺点

  1. 数组的插入和移除是需要比较大成本的，因为每次操作，都需要移动大量的元素
  2. 数组是需要指定一块相对大小的内存

数组的优点

  1. 可以很方便的取出某一个位置的值，适合用于检索数据

链表的缺点

  1. 每次寻找数据都要遍历所有的节点，不适用与检索数据，适合存储数据

链表的优点

  1. 链表存储数据只要修改引用地址，其成本减少很多。
  2. 链表不需要指定内存大小，相对灵活，适合存储数据

这其中的链表又分为单向链表和双向链表。其各自的缺点如下:

单向链表的缺点

可以到达下一个节点，但是回到上一个节点很难，需要重新遍历

双向链表的缺点

  1. 每次插入或者删除，需要处理四个节点的引用
  2. 占用的内存空间更大

综上比较

  1. 数组适合用于检索数据的场景
  2. 链表适用于存储数据的场景
  3. 单向链表占用的内存空间比较小，但是回到上一个节点，比较难
  4. 双向链表占用的空间比较大，每次插入删除，需要考虑四种场景，较复杂，但是回到上一个节点比较简单。

单向链表的实现

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

function SingleLinked(){
    function Node(element){
        this.element = element;
        this.next = null;
    }
    this.head = null;
    this.length = 0;
    // 添加元素
    SingleLinked.prototype.append = function(element){
        var current = this.head;
        var newNode = new Node(element);
        if(this.head === null) {
            this.head = newNode;
        }else {
            while(current.next){
                current = current.next;
            }
            current.next = newNode;
        }
        this.length ++;
    }
    // 插入元素
    SingleLinked.prototype.insert = function (position,element) {
        if(position < 0 || position > this.length )return false;
        var newNode = new Node(element);
        var current = this.head;
        var prev = null;
        if(position === 0){
            newNode.next = this.head;
            this.head = newNode;
        }else{
            var index = 0;
            while(index < position ){
                prev = current;
                current = current.next;
                index++;
            }
            prev.next = newNode;
            newNode.next = current;
        }
        this.length++;
        return true;
    }
    // toString方法
    SingleLinked.prototype.toString = function(){
        var str = '';
        var current = this.head;
        while(current){
            str += ','+current.element;
            current = current.next;
        }
        return str.slice(1);
    }
    //位置移除
    SigleLinked.prototype.removeAt = function(position){
        if(position < 0 || position > this.length || this.head === null )return null;
        var current = this.head;
        var prev = null;
        if(position === 0){
            if(this.length === 1){
                this.head = null;
            }else{
                this.head = this.head.next;
            }
        }else {
            var index = 0;
            while(index < position){
                prev = current;
                current = current.next;
                index ++;
            }
            prev.next = current.next;
        }
        this.length -- ;
        return current.element;
    }
    // 检索
    SingleLinked.prototype.indexOf = function(element){
        var current = this.head;
        var index = 0;
        while(current){
            if(current.element === element){
                return index;
            }
            current = current.next;
            index ++;
        }
        return -1;
    }
    // 根据元素移除
    SingleLinked.prototype.remove = function(element){
        var index = this.indexOf(element);
        return this.removeAt(index)
    }
    //判断链表是否为空
    SingleLinked.prototype.isEmpty = function(){
        return this.length === 0;
    }
    // 获取第一个节点
    SingleLinked.prototype.firstNode = function(){
        return this.head.element;
    }
}

//测试
var lk = new Linked()
lk.append(1)
lk.append(2)
lk.append(3)
lk.append(4)
lk.append(5)
lk.append(6)
lk.append(7)
lk.append(8)
alert(lk)

双向链表的实现

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
143
144
145
146
147
148
149
150
151
152
153
154
155
function DoubleLinkNode(){
        function Node(element){
          this.element = element;
          this.next = null;
          this.prev = null;
        }
        this.length = 0;
        this.head = null;
        this.tail = null;
        // 在链表的最后面加元素
        DoubleLinkNode.prototype.append = function(element){
          var newNode = new Node(element);
          if(this.head == null){
            this.head = newNode;
            this.tail = newNode;
          }else{
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
          }
          this.length ++ ;
        }
        //正向遍历
        DoubleLinkNode.prototype.forwardSting = function(){
          var current = this.head;
          var str = '';
          while(current){
            str += ','+current.element;                        
            current = current.next;
            
          }
          return str.slice(1);
        }
        //反向遍历
        DoubleLinkNode.prototype.backwardString = function(){
          var current = this.tail;
          var str = '';
          while(current){
            str += ','+current.element;            
            current = current.prev;
          }
          return str.slice(1);
        }
        // 任意位置插入
        DoubleLinkNode.prototype.insert = function(position,element){
          var newNode = new Node(element);
          if(position<0||position>this.length)return false;
          var newNode = new Node(element);
          
          var current = this.head;
          if(position === 0){
            if(this.head === null){
              this.head = newNode;
              this.tail = newNode;
            }else{
              this.head.prev = newNode;
              newNode.next = this.head;
              this.head = newNode;
            }
          }else if(position === this.length){
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
          }else{
            var index = 0;
            while(index < position){
              prev = current;
              current = current.next;
              index++;
            }
            current.prev = newNode;
            prev.next = newNode;
            newNode.next = current;
            newNode.prv = prev;
          }
          this.length ++;
          return true;
        }
        //根据位置移除节点
        DoubleLinkNode.prototype.removeAt = function(position){
          if(position < 0 || position >= this.length) return false;
          var current = this.head;
          if (position === 0) {
            if (this.length === 1) {
              this.head = null;
              this.tail = null;
            }else {
              this.head = current.next;
              this.head.prev = null;
            }
          }else if (position === this.length - 1) {
            current = this.tail;
            this.tail = current.prev;
            this.tail.next = null;
          }else{
            var index = 0;
            while (index < position){
              prev = current;
              current = current.next;
              index++;
            }
            prev.next = current.next;
            current.next.prev = prev;
          }
          this.length --;
        }
        // 根据元素，得出位置
        DoubleLinkNode.prototype.indexOf = function(element){
          current = this.head;
          var index = 0;
          while(current){
            if(element === current.element){
              return index;
            }
            current = current.next
            index ++ ;
          }
          return -1;
        }
        // 根据元素位置移除
        DoubleLinkNode.prototype.remove = function(element) {
          var index = this.indexOf(element)
          return this.removeAt(index);
        }
        //判断是否是空
        DoubleLinkNode.prototype.empty = function(){
          return this.length === 0;
        }
        // 获取第一个元素
        DoubleLinkNode.prototype.firstNode = function(){
          return this.head.element;
        }
        // 获取最后一个元素
        DoubleLinkNode.prototype.lastNode = function(){
          return this.tail.element;
        }
      }
      //测试
      var d = new DoubleLinkNode();
      d.append(1);
      d.append(2);
      d.append(3);
      d.append(4);
      d.append(5);
      d.append('a')
      //alert(d.forwardSting());
      //alert(d.backwardString());
      d.removeAt(0);
      //alert(d.forwardSting());
      alert(d.length)
      d.removeAt(3);
      alert(d.length)
      alert(d.backwardString());
      alert(d.forwardSting())
      alert('a的前置位置在'+d.indexOf('a'))