自己动手写链表

发表于 | 分类于 | | 热度: ℃
字数统计: 2.3k | 阅读时长 ≈ 10

什么是链表

链表是一种重要的数据结构，是一种数据的存储方式。链表由多个链表元素组成，每个元素称为节点。链表存储的物理结构可能是连续的，但也可能是无序的。但是链表之间的元素（节点）是有序的逻辑相连。

avatar

链表是一种很灵活的数据结构，它不需要指定内存的大小，删除节点不需要要像数组那样讲数据整体向前移动，只需要更改节点的指向。但是链表的结构也决定了它的许多缺点，比如说访问需要遍历元素，不能像数组那样依靠索引，还有就是链表每个元素存的是一个对象，这是一笔非常大的内存开销。

链表从方向可以分为单向链表，双向链表。
从结构上可以分为单链表，环形链表。

avatar

Java代码实现

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
/**
 * @author Lin
 * @date 2019-04-17 18:55
 **/
public class LinkedList<E> {
  /**
   * 节点
   */
  private class Node{

    /**
     * 节点里面的元素内容
     */
    private E e;
    /**
     * 指向下一个节点
     */
    private Node next;

    public Node(E e,Node next){
      this.e=e;
      this.next=next;
    }

    public Node(E e){
      this.e=e;
      this.next=null;
    }

    public Node(){
      this.e=null;
      this.next=null;
    }
  }

  /**
   * 虚拟链表头，让add更加有逻辑
   */
  private Node dummyHead;
  /**
   * 链表大小
   */
  private int size;

  public LinkedList(){
    dummyHead=new Node();
    size=0;
  }

  public int getSize(){
    return this.size;
  }

  public boolean isEmpty(){
    return this.size==0;
  }

  /**
   * 链表添加头元素
   * @param e 元素
   */
  public void addFirst(E e){
    add(0,e);
  }

  /**
   * 指定位置添加元素
   * @param index 索引
   * @param e 元素
   */
  public void add(int index,E e){
    if (index<0||index>size){
      //当index非法排除异常
      throw new IllegalArgumentException("the index is not valid");
    }else {
      //获取要插入的元素的前面的元素
      Node pre=dummyHead;
      for (int i = 0 ; i < index ; i ++){
        //遍历
        pre = pre.next;
      }
      //首先调用的是new Node(e,pre.next)
      //为的是让新节点的next节点指向它要添加位置的前面一个元素的原来的next节点
      //再进行赋值操作为了将添加节点前面的节点的next改为该元素
      pre.next = new Node(e,pre.next);
      size ++;
    }
  }

  /**
   * 在链表末尾加入元素
   * @param e 元素
   */
  public void addLast(E e){
    add(size,e);
  }

  /**
   * 获取某个索引的元素
   * @param index 索引
   * @return 元素
   */
  public E get(int index){
    if (index<0||index>size){
      throw new IllegalArgumentException("the index is not valid");
    }else{
      Node currentNode=dummyHead.next;
      for (int i=0;i<index;i++){
        currentNode=currentNode.next;
      }
      return currentNode.e;
    }
  }

  public E getFirst(){
    return get(0);
  }

  public E getLast(){
    return get(size-1);
  }

  /**
   * 修改元素
   * @param index 索引
   * @param e 更新后的元素
   */
  public void set(int index,E e){
    if (index<0||index>=size){
      throw new IllegalArgumentException("the index is not valid");
    }else {
      Node currentNode=dummyHead.next;
      for (int i=0;i<index;i++){
        currentNode=currentNode.next;
      }
      currentNode.e=e;
    }
  }

  /**
   * 是否包含某个元素
   * @param e 元素
   * @return 布尔
   */
  public boolean contains(E e){
    Node currentNode=dummyHead.next;
    for (int i=0;i<size-1;i++){
      if (currentNode.next!=null){
        if ((currentNode.e).equals(e)){
          return true;
        }
      }
    }
    return false;
  }

  /**
   * 移除某个索引元素
   * @param index
   * @return
   */
  public E remove(int index){
    if (index<0||index>=size){
      throw new IllegalArgumentException("the index is not valid");
    }else {
      Node currentNode=dummyHead;
      for (int i=0;i<index;i++){
        currentNode=currentNode.next;
      }
      //暂存被删除的节点
      Node tempNode=currentNode.next;
      //将遍历到的节点（被删除节点前面一个）的next指向被删除节点的next节点
      currentNode.next=tempNode.next;
      //将被删除的节点的next指向为null
      tempNode.next=null;
      size--;
      return tempNode.e;
    }
  }

  public E removeLast(){
    return remove(size-1);
  }

  public E removeFirst(){
    return remove(0);
  }

  public void remove(E e){
    Node currentNode=dummyHead.next;
    //遍历到节点的next为空
    while (currentNode!=null){
      //判断是否与需要判断的元素相等，如果相等则删除
      if (currentNode.e.equals(e)){
        Node tempNode=currentNode.next;
        currentNode.next=tempNode.next;
        tempNode.next=null;
        size--;
        return;
      }
      if (currentNode.next!=null){
        currentNode=currentNode.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
/**
 * @author Lin
 * @date 2019-04-17 20:28
 **/
public class LinkedListStack<E> implements Stack<E> {

  private LinkedList<E> linkedList;

  public LinkedListStack(){
    this.linkedList=new LinkedList<>();
  }
  @Override
  public int getSize() {
    return linkedList.getSize();
  }

  @Override
  public boolean isEmpty() {
    return linkedList.isEmpty();
  }

  @Override
  public void push(E o) {
    linkedList.addFirst(o);
  }

  @Override
  public E pop() {
    return linkedList.removeFirst();
  }

  @Override
  public E peek() {
    return linkedList.getFirst();
  }
}

链表和数组实现栈的比较

从复杂度来考虑，数组和链表实现的出栈入栈等操作的复杂度都相同，我们这里来测试一下。测试代码如下：

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
// 测试使用stack运行opCount个push和pop操作所需要的时间，单位：秒
private static double testStack(Stack<Integer> stack, int opCount){

  long startTime = System.nanoTime();

  Random random = new Random();
  for(int i = 0 ; i < opCount ; i ++) {
    stack.push(random.nextInt(Integer.MAX_VALUE));
  }
  for(int i = 0 ; i < opCount ; i ++) {
    stack.pop();
  }
  long endTime = System.nanoTime();

  return (endTime - startTime) / 1000000000.0;
}

public static void main(String[] args) {

  int opCount = 100000;

  ArrayStack<Integer> arrayStack = new ArrayStack<>();
  double time1 = testStack(arrayStack, opCount);
  System.out.println("ArrayStack, time: " + time1 + " s");

  LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
  double time2 = testStack(linkedListStack, opCount);
  System.out.println("LinkedListStack, time: " + time2 + " s");

  // 其实这个时间比较很复杂，因为LinkedListStack中包含更多的new操作
}

结果如下：
avatar

其实这个测试结果不会是稳定的，相比较之下，他们的快慢主要和环境有很大关系。

当然，ArrayStack在添加元素时可能会执行扩容操作，这个时间复杂度是O(n)的，在LinkedListStack添加元素的时候虽然没有扩容的操作但是它会执行大量new对象操作，这也是非常占用资源的。总体来说，它们的增添和删除元素的时间复杂度都是O(1),所以可以说它们执行时间的差异并不是很大。

avatar

链表实现队列

前面一篇文章专门讲到了Queue，队列就是（FIFO）的数据结构，我们主要去实现队列的入队（在队尾添加元素），出队（在队首删除元素）。回想我们前面实现的链表，在队首删除元素容易（时间复杂度是O1的），但是要在队尾添加元素就非常繁琐了，我们需要遍历整个链表，当数据量一大，我们的执行时间就会变得非常大，所以我们为了效率考虑，我们需要添加一个尾节点。

这时候我们怎么实现队列的操作呢？其实很简单，当我们入队的时候只需要将尾节点的next指向当前入队的新的节点，当然我们不得不把所有尾节点的next都置为null，为的是我们的逻辑和效率，浪费一个空间也不是大问题。

而当我们进行出队操作时，我们只需要将原来头结点变为原来头结点的next节点，返回出队节点的时候我们只需要将被删除的头结点的next节点变为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
/**
 * @author Lin
 * @date 2019-04-18 19:13
 **/
public class LinkedListQueue<E> implements Queue<E> {

  private class Node{
    private E e;
    private Node next;

    public Node(E e){
      this.e=e;
      this.next=null;
    }

  }

  private Node head,tail;
  //维持链表元素个数
  private int size;

  public LinkedListQueue(){
    head=null;
    tail=null;
    size=0;
  }

  /**
   * 入队只能从尾部
   * @param e 元素
   */
  @Override
  public void enqueue(E e) {
    //如果尾节点为空，那么就代表整个链表为空
    if (tail==null){
      //需要将元素赋值给头节点和尾节点
      head=new Node(e);
      tail=head;
      size++;
    }else {
      //不为空则需要新节点赋值给尾节点的next
      tail.next=new Node(e);
      //尾节点变换
      tail=tail.next;
      size++;
    }
  }

  /**
   * 出队操作，只能从第一个出队
   * @return 头节点
   */
  @Override
  public E dequeue() {
    //当链表为空时无法进行出队操作
    if (size==0){
      throw new IllegalArgumentException("the linkedListQueue is empty!");
    }else {
      Node tempNode=head;
      //将原来头结点的next变为当前头结点
      head=head.next;
      //将要返回的“头结点”的next置为null
      tempNode.next=null;
      size--;
      return tempNode.e;
    }
  }

  @Override
  public int getSize() {
    return this.size;
  }

  @Override
  public E getFront() {
    return head.e;
  }

  @Override
  public boolean 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Main {
  private static double testQueue(Queue<Integer> q, int opCount){

    long startTime = System.nanoTime();

    Random random = new Random();
    for(int i = 0 ; i < opCount ; i ++){
      q.enqueue(random.nextInt(Integer.MAX_VALUE));
    }

    for(int i = 0 ; i < opCount ; i ++){
      q.dequeue();
    }


    long endTime = System.nanoTime();

    return (endTime - startTime) / 1000000000.0;
  }

  public static void main(String[] args) {

    int opCount = 100000;

    ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
    double time1 = testQueue(arrayQueue, opCount);
    System.out.println("ArrayQueue, time: " + time1 + " s");

    LoopQueue<Integer> loopQueue = new LoopQueue<>();
    double time2 = testQueue(loopQueue, opCount);
    System.out.println("LoopQueue, time: " + time2 + " s");

    LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
    double time3 = testQueue(linkedListQueue, opCount);
    System.out.println("LinkedListQueue, time: " + time3 + " s");
  }
}

这个时候我们能得到结果：
avatar

通过我们实践和分析，链表实现的队列也是O(1)的时间复杂度。

-------------本文结束感谢阅读-------------
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多