序言
我们都了解链表是一种数据的存储结构,在Java使用中逻辑与c++,c语言数据结构别无二致,但主要由于Java中不存在指针的说法,从而导致在实现过程中的代码不同,所以在学习的过程中我们无需过于担心,逻辑都是想通的,此博客就是针对Java中的主流两种链表进行介绍。
一.单链表
定义:一组存储单元被用来存储线性表的数据元素 所构成的结构被称为链表
在Java中每个数据元素我们以链节称之,以下就是单链表的逻辑结构:
由上图所示每个链节都含有两部分内容 1.数据 2.下一个链节的地址
头结点:一般情况下,为了处理方便,在单链表的第一个节点之前附设一个节点或者就以第一个节点为头结点。添加头结点便于对链表的处理
单链表是非随机存取的存储结构,要取得第i个数据元素必须从头结点出发顺序寻找,也称为顺序存取的存取结构。
单链表的代码实现:
以上就是一个节点内部类的实现 ListNode next 就是指向下个节点
cur=cur.next; //代表cur指向了cur的下一个节点
1.插入链表节点的代码 分为首插,尾插,和中间部分插入
2.查找操作:判断链表是否存在该数据
3.删除单个元素以及删除数据等于该数据的所有节点:
4.计算单链表长度:
5.遍历链表:
6.清空链表:
结尾
单链表只要明确节点结构特点注重节点描述 访问时避免野地址的访问 单链表作为一种简单的数据结构 希望读者能够多联系即可掌握。
二.双链表
顾名思义 在双链表节点中有两个指向域,一个指向直接后继,一个指向指向前驱,节点如下设计:
需要在双链表中为方便访问定义一个头结点与一个尾节点
1.双链表的插入:
2.双链表的查找:
3.双链表的删除:
4.双链表长度:
三,单链表与双链表的优缺点
单链表是一种链式存储的线性表,每个节点包含数据域和指向下一节点的指针域。优点是结构简单,存储开销小,易于实现插入和删除操作(特别是在链表头部或中间位置)。例如,要在单链表的头部插入一个新节点,只需让新节点的指针指向原头部节点,再将新节点设为头部即可。缺点是只能单向遍历,查找一个节点的前驱节点比较麻烦,时间复杂度高。
双链表每个节点有两个指针域,分别指向前驱和后继节点。其优点是可以双向遍历,方便查找前驱和后继节点,在某些操作上更灵活。比如在需要频繁前后移动的场景中效率更高。缺点是每个节点的存储开销较大,因为多了一个指针域,并且插入和删除操作的代码相对复杂,要同时处理前驱和后继节点指针的更新。
关于链表一些做题代码大家可以在此链接中查询:linkedList/src/linkedList.java · 王昕/Java进行之路 - 码云 - 开源中国