Java链表入门(超详细)-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java链表入门(超详细)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

什么是链表

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

java链表,数据结构,链表,java,数据结构
那么什么是链表呢??

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

那么这是链表吗,是的,但是究竟是什么意思呢
java链表,数据结构,链表,java,数据结构

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

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

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

创建链表

–> 怎么创建一个链表呢 <–
java链表,数据结构,链表,java,数据结构

1. 创建一个结点

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

//结点类  采用内部类
private static class Node{
	//值
	public int value;
	// Node 节点类型,引用当前结点的下一个结点
	public Node next; 
	
	//构造方法初始化
	/**
     * @param value 值
     */
    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(){}

太多了吧!!! java链表,数据结构,链表,java,数据结构

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

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

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下表,将要加入的元素插入到下标位置

– 头插

java链表,数据结构,链表,java,数据结构

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

插入一个元素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;
        }
        /*
        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 < 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;
        }


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

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

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);
	// 在起始位置插入0
	list.add(0, 0); // add(index, elem): 在index位置插入元素elem
	System.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，否则返回		false
	if(!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位置的元素设置为elem
	System.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());
}

运行结果
java链表,数据结构,链表,java,数据结构

LinkedList 和 ArrayList 的区别

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
头插	需要搬移元素，效率低O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁