链表

单链表的概念

任何数据结构的基础都是创建+增删改查，由这几个操作可以构造很多算法题，所以我们也从这五项开始学习链表。

什么是链表

首先看一下什么是链表？使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。例如，使用链表存储 {4，,15，,7，,40}，各个元素在内存中的存储状态可能是：如下图：

创建链表

JVM 里有栈区和堆区，栈区主要存引用，也就是一个指向实际对象的地址，而堆区存的才是创建的对象，例如我们定义这样一个类：

1
2
3
4


public class Course{
int val;
Course next;
}

这时候 next 就指向了下一个同为 Course 类型的对象了，例如： JVM工作原理这里通过栈中的引用（也就是地址）就可以找到 val(1)，然后 val(1)结点又存了指向 val(2)的地址，而 val(3)又存了指向 val(4)的地址，所以就构造出了一个链条访问结构。

Java 规范的链表定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public class ListNode{
  private int data;
  private ListNode next;
  public ListNode(int data){
    this.data = data;
  }
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public ListNode getNext() {
        return next;
    }
    public void setNext(ListNode next) {
        this.next = next;
    }
}

LeetCode 中的链表定义

1
2
3
4
5
6
7
8
9


public class ListNode{
  private int val;
  private ListNode next;
  ListNode(int x){
    val=x;
    next=null;
  }
}
ListNode listnode = new ListNode(1);

创建对象后能直接使用 listnode.val 和 listnode.next 来操作

链表的增删改查

遍历链表

对于单链表，不管进行什么操作，一定是从头开始逐个向后访问，所以操作之后是否还能找到表头非常重要。一定要注意"狗熊掰棒子"问题，也就是只顾当前位置而将标记表头的指针丢掉了。

1
2
3
4
5
6
7
8
9


public static int getListLength(Node head){
  int length = 0;
  Node node = head;
  while(node != null){
      length++;
      node = node.next;
  }
  return length;
}

链表插入

插入操作需要要考虑三种情况：首部、中部和尾部

在链表的表头插入
在链表中间插入
在单链表的结尾插入结点

完整实现

 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


/**
     * 链表插入
     * @param head       链表头节点
     * @param nodeInsert 待插入节点
     * @param position   待插入位置，从1开始
     * @return 插入后得到的链表头节点
     */
public static Node insertNode(Node head, Node nodeInsert, int position) {
    if (head == null) {
        //这里可以认为待插入的结点就是链表的头结点，也可以抛出不能插入的异常
        return nodeInsert;
    }
    //已经存放的元素个数
    int size = getLength(head);
    if (position > size+1  || position < 1) {
        System.out.println("位置参数越界");
        return head;
    }

    //表头插入
    if (position == 1) {
        nodeInsert.next = head;
        head = nodeInsert;
        return head;
    }

    Node pNode = head;
    int count = 1;
    //这里position被上面的size被限制住了，不用考虑pNode=null
    while (count < position - 1) {
        pNode = pNode.next;     //从head开始遍历，找到目的节点
        count++;
    }
    nodeInsert.next = pNode.next;
    pNode.next = nodeInsert;

    return 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


/**
     * 删除节点
     * @param head     链表头节点
     * @param position 删除节点位置，取值从1开始
     * @return 删除后的链表头节点
     */
public static Node deleteNode(Node head, int position) {
    //判断链表是否空
    if (head == null) {
        return null;
    }
    int size = getListLength(head);
    //思考一下，这里为什么是size，而不是size+1（链表最长为size,删除不了size+1的结点）
    if (position > size || position <1) {
        System.out.println("输入的参数有误");
        return head;
    }
    if (position == 1) {
        //curNode就是链表的新head
        return head.next;
    } else {
        Node cur = head;
        int count = 1;
        while (count < position - 1) {
            cur = cur.next; //从head开始遍历，找到目的节点
            count++;
        }
        Node curNode = cur.next;
        cur.next = curNode.next;
        //上面两行可以直接简化成：cur.next=cur.next.next
    }
    return head;
}

问题

1.理解 Java 是如何构造出链表的
2.链表增加元素，首部、中间和尾部分别会有什么问题，该如何处理？
3.链表删除元素，首部、中间和尾部分别会有什么问题，该如何处理？
4.双向链表是如何构造的，如何实现元素的插入和删除。