Java链表入门 超详细

• 什么是链表
• 创建链表
• • 1. 创建一个结点
  • 2. 插入一个结点
  • • -- 头插
    • -- 尾插
    • -- 指定位置插入
  • 3.查找是否包含关键字key是否在单链表当中
  • 4.删除元素
  • • --删除第一次出现关键字为key的节点
    • --删除所有值为key的节点
  • 4.得到单链表的长度
  • 5.清空链表
  • 6.打印链表
  • 7.反转链表
  • 8.返回中间结点
  • 9.创建一个链表
• 无头结点单向链表
• 双向循环链表
• Java标准库中的链表
• LinkedList 和 ArrayList 的区别

什么是链表

说起链表,可以说是让刚接触数据结构的同学非常懵逼的

那么什么是链表呢??

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

那么这是链表吗,是的,但是究竟是什么意思呢

其实,链表就像是解密游戏一样,只有到达一个地点,才会有NPC给你下一个地点的地图,从而才能知道下个地点的位置
所以链表也是一样,对于一个链表,一个结点除了要保存结点自身的值以外,还需要保存下一个结点的地址.

这是一个简单链表的单个结点,val代表当前结点存储的值,next是一个引用,指向下一个结点
由于Java中不存在指针,所以结点通常为一个类,而next则是一个结点类实例的引用

可以看到,每一结点都保存了下一个节点的地址,所以,链表不要求每个结点中的地址空间连续

创建链表

–> 怎么创建一个链表呢 <–

1. 创建一个结点

上面说到,链表是由一个一个的结点组成,后一个结点依靠前一个才能找到,那么如何构造结点呢?
在Java中,我们用一个类来表示结点这个结构

//结点类  采用内部类private static class Node{//值public int value;// Node 节点类型,引用当前结点的下一个结点public Node next; //构造方法初始化    public Node(int value){        this.value = value;        next = null;    }}

节点创建完毕,那么,链表究竟有些什么操作呢?

//头插法        public void addFirst(int value){}        //尾插法        public void addLast(int value){}        //任意位置插入,第一个数据节点为0号下标        public boolean addIndex(int index,int value){return false;}        //查找是否包含关键字key是否在单链表当中        public boolean contains(int key){return false;}        //删除第一次出现关键字为key的节点        public void remove(int key){}        //删除所有值为key的节点        public void removeAllKey(int key){}        //得到单链表的长度        public int size(){return -1;}        public void display(){}        public void clear(){}

太多了吧!!!

接下来,一起欣赏每个方法具体如何实现

再此之前,我们要先创建一个链表,此处采用手工创建方法,具体方法后面演示.

public void createLinkedList(){        Node node = new Node(0);        Node node1 = new Node(1);        Node node2 = new Node(2);        Node node3 = new Node(3);        Node node4 = new Node(4);        //创建一个链表        head = node;        node.next = node1;        node1.next  = node2;        node2.next = node3;        node3.next = node4;    }

2. 插入一个结点

插入一个结点的方式一般有三种,一种头插法,一种尾插法,最后一种指定位置加入元素

头插法 : 在链表的起始位置加入一个元素
尾插法 : 在链表的末尾位置加入一个元素
指定位置插入 : 调用方法时传入index下表,将要加入的元素插入到下标位置

– 头插

由上述代码创建的链表就长这个样子啦

插入一个元素6,就变成如下模样~~

那么,代码呢!!

//头插法    public void addFirst(int val) {        //根据值创建新结点        Node node = new Node(val);        //判断链表是否为空        if(size == 0){            this.head = node;        }else {            //链表不为空            node.next = head;            head = node;        }        //元素个数+1        this.size++;    }

– 尾插

和头插法相似,插入后的链表长这个样子

注意:因为这是单向链表,所以,要想插入到最后一个位置,需要遍历链表.
具体代码如下

//尾插法    public void addLast(int val) {        //根据值创建新结点        Node node = new Node(val);        //判断链表是否为空        if (size == 0) {            this.head = node;        } else {            //链表不为空            //创建临时变量记录头结点,防止遍历后找不到头结点            Node tmpHead = head;            Node cur = tmpHead.next;            while (cur != null) {                tmpHead = cur;                cur = cur.next;            }            // 循环结束后,tmpHead为最后一个结点            tmpHead.next = node;        }        this.size++;    }

– 指定位置插入

对于指定位置插入,需要用户数据需要插入的位置.
如须在上述链表中index = 2 的位置插入10,链表如下

!!! : 第一个元素下标为 0

//任意位置插入,第一个数据节点为0号下标    public boolean addIndex(int index, int val) {        //判断index是否合理        if(index < 0 || index > this.size){            System.out.println("输入下标不合理...");            return false;        }        Node node = new Node(val);        Node tmpHead = this.head;        //如果index为0进行头插        if(index == 0){            node.next = head;            head = node;            return true;        }        //循环结束后,tmpHead 在待插入位置的前一个位置        while (index > 1){            tmpHead = tmpHead.next;            index--;        }        node.next = tmpHead.next;        tmpHead.next = node;        this.size++;        return true;    }

插入操作到此结束

3.查找是否包含关键字key是否在单链表当中

遍历链表,按个查找即可

//查找是否包含关键字key是否在单链表当中    public boolean contains(int key) {        //记录头结点        Node next = this.head;        //遍历每一个结点        while (next != null) {            //如果找到,返回true            if (next.value == key) {                return true;            }            next = next.next;        }        //未找到,返回 false        return false;    }

4.删除元素

–删除第一次出现关键字为key的节点

关键之处在于
node = next;
next = next.next;

//删除第一次出现关键字为key的节点    public void remove(int key) {        if (!contains(key)) {            System.out.println("没有该元素");        }        Node next = this.head;        Node node = next;        //判断第一个元素        if (next.value == key) {            this.head = next.next;            next.next = null;            this.size--;            return;        }        //循环判断后续元素        while (next != null) {            if (next.value == key) {                //跳过中间元素                node.next = next.next;                //置空                next.next = null;                //元素减一                this.size--;                return;            }            //让 next 始终在 node 的下一个元素            node = next;            next = next.next;        }    }

–删除所有值为key的节点

与删除一个元素不同的是,删除所有key值元素在循环判断时找到指定元素时不退出,继续进行查找,直到链表遍历完成.

//删除所有值为key的节点    public void removeAllKey(int key) {        if (this.head == null) {            return;        }        Node cur = this.head.next;        Node pre = this.head;        //遍历整个链表,判断每个元素        while (cur != null) {            if (cur.value == key) {                // 跳过 指定元素                pre.next = cur.next;            } else {                pre = cur;            }            cur = cur.next;        }                if (this.head.value == key) {            this.head = this.head.next;        }    }

4.得到单链表的长度

//得到单链表的长度 public int size() {        return this.size;    }

5.清空链表

直接使用 this.head = null;可以达到一样的效果,但此处对每个结点引用置空.

public void clear() {        this.size = 0;        Node tmp;        while (head.next != null) {            tmp = this.head.next;            //置空            head.next = null;            head = tmp;        }        this.head = null;    }

6.打印链表

//打印链表    public void display() {        Node tmp = this.head;        System.out.print("[");        while (tmp != null) {            if (tmp.next == null) System.out.print(tmp.value);            else System.out.print(tmp.value + ",");            tmp = tmp.next;        }        System.out.println("]");    }

7.反转链表

反转链表的核心在于,需要一个pre记录下一个结点是否为空,因为在程序运行过程中,cur会断开与下一个节点的连接,所以需要单独添加引用记录.

  //反转链表    public Node reverse() {        if (this.size == 0) {            return null;        }        if (head.next == null) {            return head;        }        Node cur = head.next;        head.next = null;        //pre记录下一个元素        Node pre;        while (cur != null) {            pre = cur.next;            cur.next = head;            head = cur;            cur = pre;        }        return head;    }

8.返回中间结点

采用快慢指针的思想,慢指针一次移动一步,快指针一次移动2步,当快指针移动到链表末尾时,慢指针就在链表中间位置

  //返回中间结点    public Node middleNode() {        Node fast = head;        Node slow = head;        while(fast != null && fast.next != null){            fast = fast.next.next;            slow = slow.next;        }        return slow;    }

9.创建一个链表

传入一个数组快速创建一个链表,实际中,根据情况做判断.

//创建一个链表public void create(int[] arr){        if(this.head != null){            System.out.println("链表不为空!");        }        Node tmp = null;        for (int i = 0; i < arr.length; i++) {            Node node = new Node(arr[i]);            if(this.head == null){                this.head = node;                tmp = this.head;            }            tmp.next = node;            tmp = tmp.next;        }        this.size = arr.length;    }

到这里为止,关于链表的基本操作就结束了…
下面是整个源码.
对于链表,以上演示的是无头单向不循环链表,对应的还有很多的不同实现的链表,如,有头双向循环链表
对于循环链表,就是每一个结点都记录了前后2个节点的引用,
对于双向链表,就是除了头结点外,还记录了尾节点.

无头结点单向链表

//无头结点单向链表public class LinkedList {    //结点类    private static class Node {        public int value;        public Node next;        public Node(int value) {            this.value = value;            next = null;        }    }    //指定头结点为空    private Node head = null;    private int size = 0;    public void createLinkedList() {        Node node = new Node(0);        Node node1 = new Node(1);        Node node2 = new Node(2);        Node node3 = new Node(3);        Node node4 = new Node(4);        //创建一个链表        head = node;        node.next = node1;        node1.next = node2;        node2.next = node3;        node3.next = node4;        size = 5;    }    //头插法    public void addFirst(int val) {        //根据值创建新结点        Node node = new Node(val);        //判断链表是否为空        if (size == 0) {            this.head = node;        } else {            //链表不为空            node.next = head;            head = node;        }        this.size++;    }    //尾插法    public void addLast(int val) {        //根据值创建新结点        Node node = new Node(val);        //判断链表是否为空        if (size == 0) {            this.head = node;        } else {            //链表不为空            //创建临时变量记录头结点,防止遍历后找不到头结点            Node tmpHead = head;            Node cur = tmpHead.next;            while (cur != null) {                tmpHead = cur;                cur = cur.next;            }            // 循环结束后,tmpHead为最后一个结点            tmpHead.next = node;        }        this.size++;    }    //任意位置插入,第一个数据节点为0号下标    public boolean addIndex(int index, int val) {        //判断index是否合理        if (index < 0 || index > this.size) {            System.out.println("输入下标不合理...");            return false;        }        Node node = new Node(val);        Node tmpHead = this.head;        //如果index为0进行头插        if (index == 0) {            node.next = head;            head = node;            return true;        }        //循环结束后,tmpHead 在待插入位置的前一个位置        while (index > 1) {            tmpHead = tmpHead.next;            index--;        }        node.next = tmpHead.next;        tmpHead.next = node;        this.size++;        return true;    }    //查找是否包含关键字key是否在单链表当中    public boolean contains(int key) {        //记录头结点        Node next = this.head;        //遍历每一个结点        while (next != null) {            //如果找到,返回true            if (next.value == key) {                return true;            }            next = next.next;        }        //未找到,返回 false        return false;    }    //删除第一次出现关键字为key的节点    public void remove(int key) {        if (!contains(key)) {            System.out.println("没有该元素");        }        Node next = this.head;        Node node = next;        //判断第一个元素        if (next.value == key) {            this.head = next.next;            next.next = null;            this.size--;            return;        }        //循环判断后续元素        while (next != null) {            if (next.value == key) {                //跳过中间元素                node.next = next.next;                //置空                next.next = null;                //元素减一                this.size--;                return;            }            //让 next 始终在 node 的下一个元素            node = next;            next = next.next;        }    }    //删除所有值为key的节点    public void removeAllKey(int key) {        if (this.head == null) {            return;        }        Node cur = this.head.next;        Node pre = this.head;        //遍历整个链表,判断每个元素        while (cur != null) {            if (cur.value == key) {                // 跳过 指定元素                pre.next = cur.next;            } else {                pre = cur;            }            cur = cur.next;        }                if (this.head.value == key) {            this.head = this.head.next;        }    }    //得到单链表的长度    public int size() {        return this.size;    }    //打印链表    public void display() {        Node tmp = this.head;        System.out.print("[");        while (tmp != null) {            if (tmp.next == null) System.out.print(tmp.value);            else System.out.print(tmp.value + ",");            tmp = tmp.next;        }        System.out.println("]");    }    //清空链表    public void clear() {        this.size = 0;        Node tmp;        while (head.next != null) {            tmp = this.head.next;            head.next = null;            head = tmp;        }        this.head = null;    }    //反转链表    public Node reverse() {        if (this.size == 0) {            return null;        }        if (head.next == null) {            return head;        }        Node cur = head.next;        head.next = null;        //pre记录下一个元素        Node pre;        while (cur != null) {            pre = cur.next;            cur.next = head;            head = cur;            cur = pre;        }        return head;    }    //返回中间结点    public Node middleNode() {        Node fast = head;        Node slow = head;        while(fast != null && fast.next != null){            fast = fast.next.next;            slow = slow.next;        }        return slow;    }    public void create(int[] arr){        if(this.head != null){            System.out.println("链表不为空!");        }        Node tmp = null;        for (int i = 0; i < arr.length; i++) {            Node node = new Node(arr[i]);            if(this.head == null){                this.head = node;                tmp = this.head;            }            assert tmp != null;            tmp.next = node;            tmp = tmp.next;        }        this.size = arr.length;    }}

双向循环链表

public class MyDoubleLinkedList {    static private class Node {        public int val;        //记录前一个结点        public Node pre;        //记录后一个结点        public Node next;        public Node(int val) {            this.val = val;            this.pre = null;            this.next = null;        }    }//记录头结点    private Node head;    //记录尾结点    private Node last;    //头插法    public void addFirst(int val) {        Node tmp = new Node(val);        if (head == null) {            head = tmp;            last = head;        } else {            tmp.next = head;            head.pre = tmp;            head = tmp;        }    }    //尾插法    public void addLast(int val) {        Node tmp = new Node(val);        if (head == null) {            head = tmp;            last = head;        } else {            last.next = tmp;            tmp.pre = last;            last = tmp;        }    }    //任意位置插入,第一个数据节点为0号下标    public void addIndex(int index, int val) {        if (index < 0 || index > size()) {            System.out.println("下标越界");        }        Node tmp = new Node(val);        Node next = head;        if(head == null){            head = tmp;            last = tmp;            return;        }        if (index == 0) {            tmp.next = head;            head.pre = tmp;            head = tmp;            return;        }        if (index == size()) {            last.next = tmp;            tmp.pre = last;            last = tmp;            return;        }        while (index > 0) {            next = next.next;            index--;        }        next.pre.next = tmp;        tmp.next = next;        tmp.pre = next.pre;        next.pre = tmp;    }    //查找是否包含关键字key是否在单链表当中    public boolean contains(int key) {        Node next = head;        while (next != null) {            if (next.val == key) {                return true;            }            next = next.next;        }        return false;    }    //删除第一次出现关键字为key的节点    public boolean remove(int key) {        if(head == null || head.next == null){            head = null;            return true;        }        if(head.val == key){            head = head.next;            head.pre = null;            return true;        }        Node tmp = head;        while (tmp.val != key){            tmp = tmp.next;            if(tmp == null){                return false;            }        }        if(tmp == last){            last.pre.next = null;            return true;        }        tmp.pre.next = tmp.next;        tmp.next.pre = tmp.pre;        return true;    }    //删除所有值为key的节点    public void removeAllKey(int key) {        boolean b = true;        while (b){            b = false;            boolean remove = remove(key);            if(remove) b = true;        }    }    //得到单链表的长度    public int size() {        int size = 0;        Node next = head;        while (next != null) {            next = next.next;            size++;        }        return size;    }    public void display() {        Node next = head;        System.out.print("[");        while (next != null) {            System.out.print(next.val + " ");            next = next.next;        }        System.out.println("]");    }    public void clear() {        while (head.next != null){            head = head.next;            head.pre = null;        }        head = null;        last = null;    }}

Java标准库中的链表

在Java标准库中,内置了一个双向链表LinkedList类

LinkedList代码演示

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()list.removeFirst(); // removeFirst(): 删除第一个元素list.removeLast(); // removeLast(): 删除最后元素list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回falseif(!list.contains(1)){list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置int elem = list.get(0); // get(index): 获取指定位置元素list.set(0, 100); // set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回List<Integer> copy = list.subList(0, 3); System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());}

运行结果

LinkedList 和 ArrayList 的区别

第一次发博客,希望大家多多支持

新人博主水平有限,如有不足,多多指正.

来源地址：https://blog.csdn.net/qq_57735833/article/details/125955522