链表——LinkedList类的概述和实现

这篇具有很好参考价值的文章主要介绍了链表——LinkedList类的概述和实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链表——LinkedList类的概述和实现,集合,java,链表,开发语言

LinkedList类

1.1LinkedList类概述

  • LinkedList类底层是基于双向链表结构实现的,不同于ArrayList类和Vector类是基于数组实现的;
  • LinkedList类是非线程安全的;
  • LinkedList类元素允许为null,允许重复元素;
  • LinkedList类插入、删除效率高,查询效率低;
  • LinkedList类基于链表实现的,因此不存在容量不足的问题,不用动态扩容;
  • 双向链表有三个区域,前指针域、数据域、后指针域。
  • LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
  • LinkedList 实现 List 接口,能对它进行队列操作。
  • LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
  • LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
  • LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
  • LinkedList 是非同步的。

1.2LinkedList类的方法

与ArrayList类相似,LinkedList类常见方法也有add()、get()、remove()、set()、size()等,用法也类似。

  • Object getFirst()        返回链表的第一个元素。
  • Object getLast()        返回链接列表的最后一个元素。
  • boolean contains(Object element)如果元素存在于列表中,则返回true。
  • void clear()                删除列表中的所有元素。 

1.3LinkedList类的特点

  • LinkedList的底层结构为双向链表,将零散的内存单元通过附加的引用关联起来体现出其顺序性,相比数组的连续空间存储,链表对内存的利用率更高;
  • 有序:插入元素的顺序和取出顺序一致;
  • 可重复:可以插入相同的元素(元素值也允许为null);
  • 插入、删除操作效率高,和ArrayList恰恰相反,按索引查找效率较低;
  • 线程不安全:没有线程锁,多个线程同步进行写操作的时候可能导致数据错误;
  • 使用场景:不会随机访问数据,更多的插入删除操作,更少的查询读取操作。 

链表

链表通常由一连串节点组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向上一个/或下一个节点的位置的链接(links

链表——LinkedList类的概述和实现,集合,java,链表,开发语言

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

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

单向链表

普通链表,也叫单链表或者单向链表(Single-Linked List)。单链表是链表中结构最简单的。

一个单链表的节点(Node)分为两个部分,第一个部分(data)保存或者显示关于节点的信息,另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。

  • 查找:单向链表只可向一个方向遍历,一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。
  • 插入:而插入一个节点,对于单向链表,我们只提供在链表头插入,只需要将当前插入的节点设置为头节点,next指向原头节点即可。
  • 删除:删除一个节点,我们将该节点的上一个节点的next指向该节点的下一个节点。

查找图:

链表——LinkedList类的概述和实现,集合,java,链表,开发语言

在表头增加节点:

链表——LinkedList类的概述和实现,集合,java,链表,开发语言

删除节点:

链表——LinkedList类的概述和实现,集合,java,链表,开发语言

2.1 单向链表的具体实现

public class SingleLinkedList {
    private int size;//链表节点的个数
    private Node head;//头节点

    public SingleLinkedList() {
        size = 0;
        head = null;
    }

    //链表的每个节点类
    private class Node {
        private Object data;//每个节点的数据
        private Node next;//每个节点指向下一个节点的连接

        public Node(Object data) {
            this.data = data;
        }
    }

    //在链表头添加元素
    public Object addHead(Object obj) {
        Node newHead = new Node(obj);
        if (size == 0) {
            head = newHead;
        } else {
            newHead.next = head;
            head = newHead;
        }
        size++;
        return obj;
    }

    //在链表头删除元素
    public Object deleteHead() {
        Object obj = head.data;
        head = head.next;
        size--;
        return obj;
    }

    //查找指定元素,找到了返回节点Node,找不到返回null
    public Node find(Object obj) {
        Node current = head;
        int tempSize = size;
        while (tempSize > 0) {
            if (obj.equals(current.data)) {
                return current;
            } else {
                current = current.next;
            }
            tempSize--;
        }
        return null;
    }

    //删除指定的元素,删除成功返回true
    public boolean delete(Object value) {
        if (size == 0) {
            return false;
        }
        Node current = head;
        Node previous = head;
        while (current.data != value) {
            if (current.next == null) {
                return false;
            } else {
                previous = current;
                current = current.next;
            }
        }
        //如果删除的节点是第一个节点
        if (current == head) {
            head = current.next;
            size--;
        } else {//删除的节点不是第一个节点
            previous.next = current.next;
            size--;
        }
        return true;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return (size == 0);
    }

    //显示节点信息
    public void display() {
        if (size > 0) {
            Node node = head;
            int tempSize = size;
            if (tempSize == 1) {//当前链表只有一个节点
                System.out.println("[" + node.data + "]");
                return;
            }
            while (tempSize > 0) {
                if (node.equals(head)) {
                    System.out.print("[" + node.data + "->");
                } else if (node.next == null) {
                    System.out.print(node.data + "]");
                } else {
                    System.out.print(node.data + "->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();
        } else {//如果链表一个节点都没有,直接打印[]
            System.out.println("[]");
        }
    }
}

测试:

public void testSingleLinkedList(){
    SingleLinkedList singleList = new SingleLinkedList();
    singleList.addHead("A");
    singleList.addHead("B");
    singleList.addHead("C");
    singleList.addHead("D");
    //打印当前链表信息
    singleList.display();
    //删除C
    singleList.delete("C");
    singleList.display();
    //查找B
    System.out.println(singleList.find("B").data);
}

打印结果:

[D->C->B->A]
[D->B->A]
B

2.2 用单向链表实现栈

栈的pop()方法和push()方法,对应于链表的在头部删除元素deleteHead()以及在头部增加元素addHead()

public class StackSingleLink {
    private SingleLinkedList link;
    
    public StackSingleLink() {
        link = new SingleLinkedList();
    }
    
    //添加元素
    public void push(Object obj) {
        link.addHead(obj);
    }
    
    //移除栈顶元素
    public Object pop() {
        Object obj = link.deleteHead();
        return obj;
    }
    
    //判断是否为空
    public boolean isEmpty() {
        return link.isEmpty();
    }
    
    //打印栈内元素信息
    public void display() {
        link.display();
    }
}

双端链表(单向引用)

对于单向链表,我们如果想在尾部添加一个节点,那么必须从头部一直遍历到尾部,找到尾节点,然后在尾节点后面插入一个节点。这样操作很麻烦,如果我们在设计链表的时候多个对尾节点的引用,那么会简单很多。

链表的节点类保留下一节点的引用(单向引用)。这就是双端链表。

双端链表:保留对头节点、尾节点的引用,可以从尾节点插入,但只能从头节点删除,只能从一个方向遍历,相当于单向链表多了一个对尾节点的引用。

双端链表的特点:双端链表的含有对第一个节点和最后一个节点的引用

双端链表的操作 读取(引用) 插入 删除
头部
尾部 x

链表——LinkedList类的概述和实现,集合,java,链表,开发语言

链表——LinkedList类的概述和实现,集合,java,链表,开发语言

注意和后面讲的双向链表的区别!!!

3.1 双端链表的具体实现

public class DoublePointLinkedList {
    private Node head;//头节点
    private Node tail;//尾节点
    private int size;//节点的个数

    private class Node {
        private Object data;
        private Node next;

        public Node(Object data) {
            this.data = data;
        }
    }

    public DoublePointLinkedList() {
        size = 0;
        head = null;
        tail = null;
    }

    //链表头新增节点
    public void addHead(Object data) {
        Node node = new Node(data);
        if (size == 0) {//如果链表为空,那么头节点和尾节点都是该新增节点
            head = node;
            tail = node;
            size++;
        } else {
            node.next = head;
            head = node;
            size++;
        }
    }

    //链表尾新增节点
    public void addTail(Object data) {
        Node node = new Node(data);
        if (size == 0) {//如果链表为空,那么头节点和尾节点都是该新增节点
            head = node;
            tail = node;
            size++;
        } else {
            tail.next = node;
            tail = node;
            size++;
        }
    }

    //删除头部节点,成功返回true,失败返回false
    public boolean deleteHead() {
        if (size == 0) {//当前链表节点数为0
            return false;
        }
        if (head.next == null) {//当前链表节点数为1
            head = null;
            tail = null;
        } else {
            head = head.next;
        }
        size--;
        return true;
    }

    //判断是否为空
    public boolean isEmpty() {
        return (size == 0);
    }

    //获得链表的节点个数
    public int getSize() {
        return size;
    }

    //显示节点信息
    public void display() {
        if (size > 0) {
            Node node = head;
            int tempSize = size;
            if (tempSize == 1) {//当前链表只有一个节点
                System.out.println("[" + node.data + "]");
                return;
            }
            while (tempSize > 0) {
                if (node.equals(head)) {
                    System.out.print("[" + node.data + "->");
                } else if (node.next == null) {
                    System.out.print(node.data + "]");
                } else {
                    System.out.print(node.data + "->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();
        } else {//如果链表一个节点都没有,直接打印[]
            System.out.println("[]");
        }
    }
}

3.2 用双端链表实现队列

public class QueueLinkedList {
    
    private DoublePointLinkedList dp;

    public QueueLinkedList() {
        dp = new DoublePointLinkedList();
    }

    public void insert(Object data) {
        dp.addTail(data);
    }

    public void delete() {
        dp.deleteHead();
    }

    public boolean isEmpty() {
        return dp.isEmpty();
    }

    public int getSize() {
        return dp.getSize();
    }

    public void display() {
        dp.display();
    }
    
}

双向链表

我们知道单向链表只能从一个方向遍历,那么双向链表(Double-Linked List)它可以从两个方向遍历。

链表——LinkedList类的概述和实现,集合,java,链表,开发语言

具体代码实现:

public class TwoWayLinkedList {
    private Node head;//表示链表头
    private Node tail;//表示链表尾
    private int size;//表示链表的节点个数

    private class Node {
        private Object data;
        private Node next;
        private Node prev;

        public Node(Object data) {
            this.data = data;
        }
    }

    public TwoWayLinkedList() {
        size = 0;
        head = null;
        tail = null;
    }

    //在链表头增加节点
    public void addHead(Object value) {
        Node newNode = new Node(value);
        if (size == 0) {
            head = newNode;
            tail = newNode;
            size++;
        } else {
            head.prev = newNode;
            newNode.next = head;
            head = newNode;
            size++;
        }
    }

    //在链表尾增加节点
    public void addTail(Object value) {
        Node newNode = new Node(value);
        if (size == 0) {
            head = newNode;
            tail = newNode;
            size++;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
            size++;
        }
    }

    //删除链表头
    public Node deleteHead() {
        Node temp = head;
        if (size != 0) {
            head = head.next;
            head.prev = null;
            size--;
        }
        return temp;
    }

    //删除链表尾
    public Node deleteTail() {
        Node temp = tail;
        if (size != 0) {
            tail = tail.prev;
            tail.next = null;
            size--;
        }
        return temp;
    }

    //获得链表的节点个数
    public int getSize() {
        return size;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return (size == 0);
    }

    //显示节点信息
    public void display() {
        if (size > 0) {
            Node node = head;
            int tempSize = size;
            if (tempSize == 1) {//当前链表只有一个节点
                System.out.println("[" + node.data + "]");
                return;
            }
            while (tempSize > 0) {
                if (node.equals(head)) {
                    System.out.print("[" + node.data + "->");
                } else if (node.next == null) {
                    System.out.print(node.data + "]");
                } else {
                    System.out.print(node.data + "->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();
        } else {//如果链表一个节点都没有,直接打印[]
            System.out.println("[]");
        }

    }
}

有序链表

前面的链表实现插入数据都是无序的,无序链表最大特点就是在头部或尾部增加新节点。在有些应用中需要链表中的数据有序。

有序链表:递增,递减或者其他满足一定条件的规则,插入数据时,从头结点开始遍历每个节点,在满足规则的地方插入新节点。

在有序链表中,数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度(因为元素不需要移动),另外链表可以扩展到全部有效的使用内存,而数组只能局限于一个固定的大小中。

public class OrderLinkedList {
    private Node head;

    private class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public OrderLinkedList() {
        head = null;
    }

    //插入节点,并按照从小打到的顺序排列
    public void insert(int value) {
        Node node = new Node(value);
        Node pre = null;
        Node current = head;
        while (current != null && value > current.data) {
            pre = current;
            current = current.next;
        }
        if (pre == null) {
            head = node;
            head.next = current;
        } else {
            pre.next = node;
            node.next = current;
        }
    }

    //删除头节点
    public void deleteHead() {
        head = head.next;
    }

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

在有序链表中插入和删除某一项最多需要O(N)次比较,平均需要O(N/2)次,因为必须沿着链表上一步一步走才能找到正确的插入位置,然而可以最快速度删除最值,因为只需要删除表头即可,如果一个应用需要频繁的存取最小值,且不需要快速的插入,那么有序链表是一个比较好的选择方案。比如优先级队列可以使用有序链表来实现。

5.1 有序链表和无序数组组合排序

比如有一个无序数组需要排序,解冒泡排序、选择排序、插入排序这三种简单的排序时,需要的时间级别都是O(N^2^)

现在我们讲解了有序链表之后,对于一个无序数组,我们先将数组元素取出,一个一个的插入到有序链表中,然后将他们从有序链表中一个一个删除,重新放入数组,那么数组就会排好序了。

和插入排序一样,如果插入了N个新数据,那么进行大概N^2^/4次比较。但是相对于插入排序,每个元素只进行了两次排序,一次从数组到链表,一次从链表到数组,大概需要2*N次移动,而插入排序则需要N^2^次移动,

效率肯定是比前面讲的简单排序要高,但是缺点就是需要开辟差不多两倍的空间,而且数组和链表必须在内存中同时存在,如果有现成的链表可以用,那么这种方法还是挺好的。

总结

上面我们讲了各种链表,每个链表都包括一个LinkedList对象和许多Node对象,LinkedList对象通常包含头和尾节点的引用,分别指向链表的第一个节点和最后一个节点。

而每个节点对象通常包含数据部分data,以及对上一个节点的引用prev和下一个节点的引用next,只有下一个节点的引用称为单向链表,两个都有的称为双向链表。

next值为null则说明是链表的结尾,如果想找到某个节点,我们必须从第一个节点开始遍历,不断通过next找到下一个节点,直到找到所需要的。

栈和队列都是ADT,可以用数组来实现,也可以用链表实现。文章来源地址https://www.toymoban.com/news/detail-633397.html

到了这里,关于链表——LinkedList类的概述和实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【JAVA语言-第15话】集合框架(二)——List、ArrayList、LinkedList、Vector集合

    目录 List集合 1.1 概述 1.2 特点 1.3 常用方法 1.4 ArrayList集合 1.4.1 概述  1.4.2 练习 1.5 LinkedList集合  1.5.1 概述 1.5.2 特点 1.5.3 常用方法 1.5.4 练习 1.6 Vector类 1.6.1 概述 1.6.2 练习 1.7 List实现类的异同点         java.util.List: List是一个接口,它继承自Collection接口。 常用的实现

    2024年01月25日
    浏览(57)
  • Java基础——LinkedList集合实现栈和队列

    (1)LinkedList的特点: 底层数据结构是双链表,查询慢,首尾操作的速度是极快的,所以多了很多首位操作的特有API。 (2)LinkedList集合的特有功能: 方法名称 说明 public void addFirst(E e) 在该列表开头插入指定的元素 public void addLast(E e) 将指定的元素追加到此列表的末尾 publ

    2023年04月12日
    浏览(46)
  • Java中List接口两个实现,ArrayList类和LinkedList类的常用方法(一)

    要了解List接口,就不得不说起Java的集合框架。 (该图来自菜鸟教程) Java 集合框架主要包括两种类型的容器,集合Collection和图Map。 Collection接口代表了 单列集合 ,它包含了一组Object元素,每个元素都有一个值。 (这里有个“泛型擦除”的概念,在此不提及有兴趣可自行了

    2024年01月19日
    浏览(39)
  • 数据结构(Java实现)LinkedList与链表(上)

    链表 逻辑结构 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 链表的实现 创建一个链表 遍历单链表 、 得到

    2024年02月11日
    浏览(53)
  • 数据结构(Java实现)LinkedList与链表(下)

    ** ** 结论 让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。 LinkedList的模拟实现 单个节点的实现 尾插 运行结果如下: 也可以暴力使用 全部代码 MyLinkedList IndexOut

    2024年02月11日
    浏览(46)
  • Java进阶(7)——手动实现LinkedList & 内部node类的实现 & 增删改查的实现 & toString方法 & 源码的初步理解

    1.linkedList的节点,当前,上一个,下一个的思想; 2.根据index找node的方法,根据index确定从头部还是尾部; 3.linkedlist的增删改查的实现,本质是改变节点的信息; 4.递归方法实现自定义链表的toString方法; Java进阶(3)——手动实现ArrayList 源码的初步理解分析 数组插入数据和

    2024年02月11日
    浏览(51)
  • Java集合之LinkedList

    目录 基本介绍  常用方法 源码解析 1. LinkedList的底层结构,Node双向链表 2. LinkedList的几个内部变量 3. getFirst() 4. removeFirst() 5. addFirst(E e) 6. contains(Object o) 7. add(E e) 8. remove(Object o) 9. addAll(int index, Collection c) 10. get(int index) 11. spliterator() 总结 LinkedList是实现了List和Deque接口的双

    2024年02月15日
    浏览(41)
  • 【Java】LinkedList 集合

    LinkedList集合特点 LinkedList 底层基于双向链表实现增删 效率非常高,查询效率非常低。 LinkedList源码解读分析 LinkedList 是双向链表实现的 List LinkedList 是非线程安全的(线程是不安全的) LinkedList 元素允许为null,允许重复元素 LinkedList 是基于链表是实现的,因此插入删除效率高

    2024年02月07日
    浏览(45)
  • Java集合之LinkedList源码篇

    ☆* o(≧▽≦)o *☆嗨~我是小奥🍹 📄📄📄个人博客:小奥的博客 📄📄📄CSDN:个人CSDN 📙📙📙Github:传送门 📅📅📅面经分享(牛客主页):传送门 🍹文章作者技术和水平有限,如果文中出现错误,希望大家多多指正! 📜 如果觉得内容还不错,欢迎点赞收藏关注哟!

    2024年01月16日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包