一篇文章带你玩转JAVA单链表_Java教程

一、链表

1. 概念

链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的

上章介绍到顺序表适合用作查询和修改，而不适合用作插入和删除。并且它增容时容易造成空间浪费。而链表则具有以下的特点

适合用作插入和删除随用随取，避免了空间的浪费不适合用作查询和修改

2. 结构

链表其实可以想象成一条被打了一些结的绳子

一篇文章带你玩转JAVA单链表

而实际上，链表就是由一个个节点构成的，只不过每个节点一般有两个域

数值域 data：里面存储数据

next 域：里面存储的是下一个节点的地址（是引用变量）

一篇文章带你玩转JAVA单链表

其中

尾节点：当这个节点的 next 域为 null 时，该节点就是尾节点

头节点：整个链表的第一个节点就是头节点

实际中的链表结构非常多，通过以下的情况的组合可以有8种链表的结构（比如带头单向循环链表就是一种）

单向、双向

带头节点、不带头

节点循环、非循环

而上图所示，就是一个单向不带头非循环链表。

一篇文章带你玩转JAVA单链表

可能有人会疑问，上述图片中不是存在头节点吗？那为啥它又是一个不带头节点的链表呢？我将上述图片实例稍稍改一下就是带头节点的了

一篇文章带你玩转JAVA单链表

我在原有的头节点前面又多了一个节点，并且这个节点的数值域里面的数据可有可无，因为对其没有影响。而这里面的头节点只是一个标志，标识这个节点是该链表的头

那带头节点的和不带头结点的链表有啥差别呢？

不带头：这个链表的头节点可能发生改

变带头：这个链表的头节点不会发生改变

那循环链表又是啥样的呢？我们可以将上述单向不带头非循环链表稍微修改一下

一篇文章带你玩转JAVA单链表

即将尾节点的 next 域存储了头节点的地址

我们知道一个节点一般就两个域，但如果是双向链表，则就有三个域了

数值域 data：里面存储数据

next 域：里面存储的是下一个节点的地址（是引用变量）

prev 域：里面存储的是上一个节点的地址（是引用变量）

我们画一个不带头双向非循环链表就是这样的

一篇文章带你玩转JAVA单链表

接下来我将主要介绍单向不带头非循环链表和双向不带头非循环链表，这两种链表也是经常出现在面试题中的

二、单向不带头非循环链表

1. 概念及结构

上述通过图解，大家应该对单向不带头非循环链表应该有了了解。那么代码中该怎么实现呢？

我们知道，链表应该可以看作一个类，而节点本身其实也可以抽象的看作成一个类

首先对于节点类，代码可以写出这样

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}

先定义了数值域，再定义了 next 域（由于 next 存储的是下一个节点的地址，故写出上述那样）。而我们初始时可以知道 val，所以可以写个构造函数对 val 进行初始化，而该节点的 next 域初始时是不可能知道的，所以不对 next 做初始化

如果创造一个 Node 对象就可以写出

Node node = new Node(10);

即头节点的数值域为10。

再定义链表类，代码可以写成这样

public class MyLinkedList {
    public Node head;
}

我们定义了一个头节点，这是我们很容易发现的，就比如我要对该链表进行头插，则该链表的头节点一直都在改变。所以写上述的代码就是为了标识单链表的头节点。

2. 链表的实现

接下来我们来实现单向不带头非循环链表的一些操作

打印链表

public void display(){
    Node cur =this.head;
    while(cur!=null){
        System.out.print(cur.val + " ");
        cur=cur.next;
    }
    System.out.println();
}

求链表的长度

public int size(){
    Node cur=this.head;
    int count=0;
    while(cur!=null){
        count++;
        cur=cur.next;
    }
    return count;
}

查找值 key 是否在单链表中

public boolean contains(int key){
    Node cur=this.head;
    while(cur!=null){
        if(key==cur.val){
            return true;
        }
        cur=cur.next;
    }
    return false;
}

清除单链表

public void clear(){
    this.head.val=0;
    this.head.next=null;
}

头插法

public void addFirst(int data){
    Node node=new Node(data);
    if(head==null){
        this.head=node;
    }else {
        node.next = this.head;
        this.head = node;
    }
}

尾插法

public void addLast(int data){
    Node node = new Node(data);
    if(this.head==null){
        this.head=node;
    }else {
        Node cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

通过下标找到前驱节点（第一个节点下标为0）

public Node searchPrev(int index){
    Node cur = this.head;
    int count=0;
    while(count!=index-1){
        cur=cur.next;
        count++;
    }
    return cur;
}

任意位置插入

public void addIndex(int index, int data){
    if(index<0 || index>size()){
        throw new RuntimeException("index 不合法");
    }
    if(index==0){
        addFirst(data);
        return;
    }
    if(index==size()) {
        addLast(data);
        return;
    }
    Node node =new Node(data);
    Node cur =searchPrev(index);
    node.next=cur.next;
    cur.next=node;
}

通过值 key 找到前驱节点（第一个节点下标为0）

public Node searchPrevNode(int key){
    Node cur = this.head;
    while(cur.next!=null){
        if(cur.next.val==key) {
            return cur;
        }
        cur=cur.next;
    }
    return null;
}

删除第一次出现的值为 key 的节点

public void remove(int key){
    if(this.head==null){
        return;
    }
    if(key==this.head.val){
        this.head=this.head.next;
        return;
    }
    Node node = searchPrevNode(key);
    if(node==null){
        System.out.println("链表中无要删除的元素");
    }else {
        node.next = node.next.next;
    }
}

删除所有出现的值为 key 的节点

public void removeAllKey(int key){
    if(this.head==null){
        return;
    }
    Node prev=this.head;
    Node cur=this.head.next;
    while(cur!=null){
        if(cur.val==key){
            cur=cur.next;
            prev.next=cur;
        }else{
            prev=cur;
            cur=cur.next;
        }
    }
    if(this.head.val==key){
        this.head=this.head.next;
    }
}

呼，写的我人傻了

一篇文章带你玩转JAVA单链表