Java数据结构——————双向链表(详细图解,增删改查详细实现)(上)

简介: 目录 1.什么是双向链表?2.双向链表的基本功能和结构3.双向链表基本功能详细图解代码实现 1.清空,判空,获得长度功能实现 2.获取第一个元素和最后一个元素 3.添加元素t 4.向指定位置i插入元素t 5.获取指定位置i处的元素 6.找到元素t第一次出现的位置 7.删除位置i的元素,并返回该元素

1.什么是双向链表?


要明白什么是双向链表,我们首先得明白什么是链表和什么是单链表?如果对于这个还有疑惑的推荐我的这篇博客,里面有非常详细的图解和代码实现。


https://blog.csdn.net/m0_57487901/article/details/120871022?spm=1001.2014.3001.5501


首先我们通过一张直观的图对比单链表和双向链表


image.png


通过名字我们就可知它之所以叫双向链表,就是它可以向两头遍历,任意一个结点我可以得到它的前结点和后一个结点。不像单链表具有单向遍历的局限性,而且双向链表同时记录了尾结点last,这样我们每次想得到最后一个结点就不需要从头遍历到末尾了,如果链表很长的话,这样每次循环查询是非常浪费时间的。


2.双向链表的基本功能和结构


public class TwoWayLinkList<T> implements Iterable {
    //首结点
     Node head;
    //链表的长度
     int N;
     Node last;
    //结点类
    public class Node {
        //数据域
        public T item;
        //头指针
        public Node pre;
        //尾指针
        public Node next;
        public Node(T item, Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }
    //初始化链表
    public TwoWayLinkList() {
        //初始化头结点和尾结点
        this.head = new Node(null, null, null);
        this.last = new Node(null, null, null);
        //初始化元素个数
        N = 0;
    }

解析:学习数据结构,我们在学习它的基本功能前,一定要明白它的逻辑结构。代码中,首先有一个内部类Node表示为结点,因为一个结点具有指针域和数据域,所以需要用一个类来表示,Node里面首先有表示存放数据的item,因为不清楚存放的数据是什么类型,所以用泛型T表示。同时有两个Node类型的变量pre和next分别记录指向前一个结点和后一个结点。在链表中有两个个Node类型的变量head和last分别表示头指针和尾指针,同时有一个int类型的N记录成员个数。初始化时,只需要建立头结点和尾结点,内部属性都为null,再让N为0即可。


public void clear() 
清空链表
public int getLength() 
获取链表长度
public boolean isEmpty()
判断链表是否为空
public T getFirst()
获取第一个元素
public T getLast()
获取最后一个元素
public void add(T t)
插入元素t
public void insert(int i,T t)
向指定位置i位置插入元素t
public T get(int i)
获取指定位置i处的元素
public int indexOf(T t)
public T remove(int i)
找到元素t第一次出现的位置
删除位置i处的元素,并返回该元素

看上去很多API功能需要实现,但其实大部分都很简单,只要理解就可以自己写出来。


3.双向链表基本功能详细图解代码实现


1.清空,判空,获得长度功能实现


//清空链表
    public void clear() {
        this.head.next = null;
        this.last = null;
        this.N = 0;
    }
    //获取链表长度
    public int getLength() {
        return N;
    }
        //判断链表是否为空
    public boolean isEmpty() {
        return N == 0;
    }

解析:这里我需要提醒大家,虽然头结点我们一般不存储元素,但是尾结点我们是可以存储的元素的,不要硬性思维。清空时,我们需要让头结点的next为null,这样无法从头进入链表,尾结点因为也是存储数据的,所以得直接让last为null,同时让N为0。获得链表长度直接返回N。判空也是直接返回N是否等于0的值即可。


相关文章
|
12月前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
12月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
81 3
|
12月前
|
分布式计算 Java 大数据
大数据-147 Apache Kudu 常用 Java API 增删改查
大数据-147 Apache Kudu 常用 Java API 增删改查
118 1
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
12月前
|
存储 缓存
数据结构3——双向链表
数据结构3——双向链表
223 1
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表:顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表,使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作,并提供了具体代码示例。静态分配方式下顺序表的长度固定,而动态分配则可根据需求调整大小。此外,还总结了顺序表的优点,如随机访问效率高、存储密度大,以及缺点,如扩展不便和插入删除操作成本高等特点。
679 5
|
存储 Java
|
Java Apache 索引
java 调用solr服务器 实现增删改查 及高亮显示
首先有几点需要注意 客户端要调用solr服务,首先要把solr服务端工程启动,即前面文章讲的把solr下的slor.war例子放在tomcat下,进行相关配置,并启动。 (1)Exception in thread "main" org.apache.solr.client.solrj.beans.BindingException: class: class solr.PeopleBe
2897 0
|
18天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案

热门文章

最新文章