Java数据结构之第五章、LinkedList与链表

简介: 由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。

 一、ArrayList的缺陷

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        // ...
// 默认容量是10
        private static final int DEFAULT_CAPACITY = 10;
        //...
// 数组:用来存储元素
        transient Object[] elementData; // non-private to simplify nested class access
        // 有效元素个数
        private int size;
        public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: " +
                        initialCapacity);
            }
        } // ...
    }

image.gif

由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java集合中又引入了LinkedList,即链表结构。


二、链表

2.1链表的概念及结构

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

image.gif编辑

实际中链表的结构非常多样,通过节点组成。以下情况组合起来就有8种链表结构:

1.单向 带头 循环链表   2.单向 带头 非循环链表   3.单向 不带头 循环链表 4.单向 不带头 非循环链表

5.双向 带头 循环链表   6.双向 带头 非循环链表   7.双向 不带头 循环链表   8.双向 不带头 非循环链表

2.1.1单向和双向

image.gif编辑

2.1.2带头或者不带头

image.gif编辑

2.1.3循环或者非循环

image.gif编辑

2.1.4重点

1.无头单向非循环链表

结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

image.gif编辑

2. 无头双向链表

在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

2.2链表的实现

// 1、无头单向非循环链表实现
public class IndexOutOfBounds extends RuntimeException{
    public IndexOutOfBounds(String message){
        System.out.println(message);
    }
}
   public class MySingleList {
    //节点的创建
    class ListNode{
        //值域
        public int val;
        //引用变量
        public ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
    //永远指向头节点
    public ListNode head;
    public void createList(){
        ListNode node1=new ListNode(12);
        ListNode node2=new ListNode(23);
        ListNode node3=new ListNode(34);
        ListNode node4=new ListNode(45);
        ListNode node5=new ListNode(56);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        head.next=node1;
    }
    public void show(){
        ListNode cur=head;
        while(cur!=null){
            System.out.println(cur.val);
            cur=cur.next;
        }
        System.out.println();
    }
    //头插法
    public void addFirst(int data){
        ListNode cur=new ListNode(data);
        cur.next=head;
        head=cur;
    }
    //尾插法
    public void addLast(int data){
        ListNode node=new ListNode(data);
        if(head==null){
            head=node;
            return ;
        }
        ListNode cur=head;
        while(cur!=null){
            cur=cur.next;
        }
        //cur 指向的节点是尾巴节点
        cur.next=node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        int len=size();
        if(index<0||index>len){
            throw new IndexOutOfBounds("任意位置插入数据的时候,index的位置不合法:"+index);
        }
        if(index==0){
            addFirst(data);
            return ;
        }
        if(index==len){
            addLast(data);
            return ;
        }
        ListNode node=new ListNode(data);
        ListNode cur=findIndex(index);
        node.next=cur.next;
        cur.next=node;
    }
    private ListNode findIndex(int index){
        ListNode cur=head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur=head;
        while(cur!=null){
            //如果value值为空,需要使用equals方法比较
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(head==null){
            return ;
        }
        if(head.val==key){
            head=head.next;
            return ;
        }
        ListNode prev=searchPrev(key);
        if(prev==null){
            System.out.println("没有这个数据!");
            return ;
        }
        ListNode del=prev.next;
        prev.next=del.next;
    }
    private ListNode searchPrev(int key){
        ListNode prev=head;
        while(prev.next!=null){
            if(prev.next.val==key){
                return prev;
            }
            else{
                prev=prev.next;
            }
        }
        return null;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head==null){
            return ;
        }
        //第一种删除头节点方法
        /*
        * while(head.val==key){
        *   head=head.next;
        * }
        * */
        ListNode cur=head.next;
        ListNode prev=head;
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }
            else{
                prev=cur;
                cur=cur.next;
            }
        }
        //第二种删除头节点方法
        if(head.val==key){
            head=head.next;
        }
    }
    //得到单链表的长度
    public int size(){
        int count=0;
        ListNode cur=head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public void clear() {
        //this.head=null;
        while(head!=null){
            ListNode HeadNext=head.next;
            head.next=null;
            head=HeadNext;
        }
    }
}

image.gif


目录
相关文章
|
6月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
167 1
|
4月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
198 3
|
11月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
174 4
|
6月前
|
Java
Java LinkedList集合的深度剖析
总的来说,我希望像说故事一样讲解Java LinkedList集合的使用和实现原理,让有些许枯燥的编程知识变得趣味盎然。在这个“公交车”故事中,你不仅熟悉了LinkedList集合的实现和使用,而且还更深入地理解了数据结构中的链表。链表可能会因为插入和删除的便利性而被选用,虽然它的查找效率并不高,但是在很多场景中仍然十分有效。这就像公交车,虽然它速度不快,但却是城市出行的重要工具。
86 8
|
6月前
|
存储 Java 编译器
Java 中 .length 的使用方法:深入理解 Java 数据结构中的长度获取机制
本文深入解析了 Java 中 `.length` 的使用方法及其在不同数据结构中的应用。对于数组,通过 `.length` 属性获取元素数量;字符串则使用 `.length()` 方法计算字符数;集合类如 `ArrayList` 采用 `.size()` 方法统计元素个数。此外,基本数据类型和包装类不支持长度属性。掌握这些区别,有助于开发者避免常见错误,提升代码质量。
478 1
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
203 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
318 25
|
9月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
347 5
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
10月前
|
存储 缓存 安全
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
146 5