小工具知识网

当前位置: 首页 > 行业知识 > Java链表入门(超详细)

行业知识

Java链表入门(超详细)

2026-11-20 07:27:09 来源:互联网转载

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则是一个结点类实例的引用

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

          创建链表

          –> 怎么创建一个链表呢 //值public int value;// Node 节点类型,引用当前结点的下一个结点public Node next; //构造方法初始化/** * @param value 值 */ public Node(int value){ this.value = value; next = null; }}} //尾插法 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(){} 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; } //根据值创建新结点 Node node = new Node(val); //判断链表是否为空 if(size == 0){ this.head = node; }else { //链表不为空 node.next = head; head = node; } //元素个数+1 this.size++; } //根据值创建新结点 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是否合理 if(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;        }        /*        Node cur = this.head.next;        Node pre = this.head;        上述代码跳过了head.value        所以需要单独判断        */        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    

          到这里为止,关于链表的基本操作就结束了…

          下面是整个源码.

          对于链表,以上演示的是无头单向不循环链表,对应的还有很多的不同实现的链表,如,有头双向循环链表

          对于循环链表,就是每一个结点都记录了前后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  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;        }        /*        Node cur = this.head.next;        Node pre = this.head;        上述代码跳过了head.value        所以需要单独判断        */        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  

            双向循环链表

            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  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类

            方法解释
            boolean add(E e)尾插 e
            void add(int index, E element)将 e 插入到 index 位置
            boolean addAll(Collection

上一篇:怎么把网页放到域名里

下一篇:揭秘,关于3306端口的关键信息揭秘,你必须了解!