链表是啥?如何搞定它?
发布日期:2021-06-29 18:13:44
浏览次数:2
分类:技术文章
本文共 7800 字,大约阅读时间需要 26 分钟。
前言
链表是一种 递归 的数据结构,或者为空 null
,或者指向一个结点(node
)的引用,一个结点含有 一个泛型元素和一个指向另一条链表的引用。
通常分为如下三种类型:
- 单向链表:结点被分成两个部分。第一个部分保存或者显示关于结点的信息,第二个部分存储下一个结点的地址,只能向一个方向遍历。
- 双向链表:每个数据结点中都有两个指针,分别指向直接后继和直接前驱。
- 循环链表:一种 链式存储结构,它的最后一个结点指向头结点,形成一个环。
单向链表
单向链表包括一个值和一个指向下一结点的指针,其典型结构定义如下:
public class Node{ // 数据对象 private Object val; // 指向后继结点 private Node next; // 无参构造函数 public Node(){ // 指向数据对象和后继结点的引用都置空 this.val = null; this.next = null; } // 有参构造函数 public Node(Object val, Node node){ this.val = val; this.next = node; } // 获取当前存放位置的数据对象 public Object getVal(){ return this.val; } // 将给定元素存放至当前位置,同时返回此前存放的数据对象 public Object setVal(Object value){ Object oldVal = this.val; this.val = value; return oldVal; } // 取当前结点后继结点 public Node getNext(){ return this.next; } // 修改当前结点后继结点 public void setNext(Node newNext){ this.next = newNext; }}
双向链表
每个数据结点中都有两个指针,分别指向直接后继和直接前驱,其典型结构定义如下:
public class DoubleNode{ // 数据对象 private Object val; // 指向前驱结点 private DoubleNode prev; // 指向后继结点 private DoubleNode next; // 无参构造函数 public DoubleNode(){ this.val = null; this.prev = null; this.next = null; } // 有参构造函数 public DoubleNode(Object value, DoubleNode previous, DoubleNode next){ this.val = value; this.prev = previous; this.next = next; } // 获取当前位置数据对象 public Object getVal(){ return val; } // 将给定元素放在当前位置,返回此前存放的元素 public Object setVal(Object value){ Object oldVal = val; val = value; return oldVal; } // 获取当前结点后继结点 public DoubleNode getNext(){ return next; } // 修改后继结点 public void setNext(DoubleNode newNext){ next = newNext; } // 获取当前位置前驱结点 public DoubleNode getPrev(){ return prev; } // 修改前驱结点 public void setPrev(DoubleNode newPrev){ prev = newPrev; }}
单向链表的增删改查
基于链表实现栈
public class MyStack{ // 指向栈顶元素(头结点) private Node head; // 栈中元素数目 private int size; // 构造方法(构造一个空栈) public MyStack(){ this.head = null; this.size = 0; } // 查询栈中元素个数 public int getSize(){ return size; } // 判断栈是否为空 public boolean isEmpty(){ return head == null; // 或者 size == 0; } // 读取栈顶(首结点信息) public Object getTop(){ if(isEmpty()){ System.out.println("栈空"); } return head.getVal(); } // 压栈(即插入首结点) public void insertAtHead(Object val){ // 创建一个新结点,将其作为首结点插入 Node node = new Node(val, head); // 更新首结点引用 head = node; // 栈中元素数目增加 size++; } // 出栈(删除首结点) public Object removeAtHead(){ if(isEmpty){ System.out.println("栈空"); } // 当前结点数据对象 Object tmp = head.getVal(); // 更新首结点引用 head = head.getNext(); size--; return tmp; }}
基于链表实现队列
public class MyQueue{ // 队列首元素(首结点) private Node head; // 队列尾元素(尾结点) private Node tail; // 队列规模 private int size; // 构造空队列 public MyQueue(){ head = null; tail = null; size = 0; } // 队列规模 public int getSize(){ return size; } // 判断当前队列是否为空 public boolean isEmpty(){ return size == 0; } // 查看队首元素 public Object getFront(){ if(isEmpty()){ System.out.println("队列为空"); } return head.getElem(); } // 入队 public void enQueue(Object val){ Node node = new Node(); // 新结点作为末结点插入 node.setVal(val); node.setNext(null); // 若当前队列为空,则直接插入 if(size == 0){ head = node; }else { // 否则将新结点接至队列末端 tail.setNext(node); } // 更新指向末结点的引用 tail = node; // 更新队列规模 size++; } // 出队 public Object deQueue(){ if(size == 0){ System.out.println("队列为空"); } Object tmp = head.getVal(); head = head.getNext(); // 更新队列规模 size--; // 队列为空时,将末结点引用置空 if(size == 0){ tail = null; } return tmp; } // 遍历队列 public void traversal(){ Node node = head; while(node != null){ System.out.println(node.getVal() + "\t"); node = node.getNext(); } }}
双向链表的增删改查
实现双向链表时,通常在最前端和最后端各设置一个 哑元结点,分别称为 头结点 和 尾结点,起着 哨兵 的作用。但实际上两者并不存储任何实质的数据对象,头(尾)结点的 next
(prev
)引用指向首(末)结点,而 prev
(next
)引用为空。
首尾结点的插入
假设要进行首结点的插入,则通常需要如下步骤,而末结点的插入则是和首结点的插入过程对称。
- 首先生成一个新结点;
- 然后将其接入队列的前端;
- 接着将头结点的
next
的引用指向新插入的结点,同时将首结点的prev
的引用指向新插入的结点。
首尾结点的删除
假设要进行末结点的删除,通常需要如下步骤,而首结点的删除过程适合尾结点的删除过程对称。
- 将新的末结点的
next
引用指向尾结点; - 同时将尾结点的
prev
引用指向新的末结点; - 最后原先的末结点将会被系统回收。
一般结点的插入与删除
要实现在一般结点之间插入新结点,通常需要进行如下步骤:
- 创建一个新的结点,然后将其
prev
引用指向前一个结点,同时将其next
引用指向后一个结点; - 然后将前一个结点的
next
引用指向新结点,同时将后一个结点的prev
引用指向新结点。
而要实现在一般结点之间删除结点,通常需要进行如下步骤:
- 首先找到要删除的结点的前驱和后继结点;
- 然后将其前驱结点的
next
引用指向后驱结点,同时将后驱结点的prev
引用指向前驱结点。
public class MyDoubleQueue{ // 指向头结点(哨兵) private DoubleNode header; // 指向尾结点(哨兵) private DoubleNode trailer; // 队列规模 private int size; // 无参构造函数 public MyDoubleQueue(){ header = new DoublNode(); trailer = new DoubleNode(); header.setNext(trailer); trailer.setPrev(trailer); size = 0; } // 获取当前队列规模 public int getSize(){ return size; } // 判断队列是否为空 public boolean isEmpty(){ return size == 0; } // 取首元素 public Object getHead(){ if(isEmpty()){ System.out.println("队列为空"); } return header.getNext().getVal(); } // 取末元素 public Objecct getTrail(){ if(isEmpty()){ System.out.println("队列为空"); } return trailer.getPrev().getVal(); } // 遍历 public void traversal(){ DoubleNode node = header.getNext(); while(node != trailer){ System.out.print(node.getVal() + "\t"); node = node.getNext(); } System.out.println(); } // 前端插入新结点 public void insertFirst(Object val){ DoubleNode second = header.getNext(); DoubleNode first = new DoubleNode(val, header, second); second.setPrev(first); header.setNext(first) size++; } // 前端删除结点 public Object removeFirst(){ if(isEmpty()){ System.out.println("队列为空"); } // first 是要删除的结点,找到要删除结点的后继结点 second DoubleNode first = header.getNext(); DoubleNode second = first.getNext(); // 要删除结点的值 Object value = first.getVal(); // 将头结点的 next 指向要删除的后继结点 second,同时将 second 的前驱结点指向头结点 header.setNext(second); second.setPrev(header); // 更新规模 size--; return value; } // 后端插入新结点 public void insertLast(Object val){ DoubleNode second = trailer.getPrev(); DoubleNode first = new DoubleNode(val, second, trailer); second.setNext(first); trailer.setPrev(first); size++; } // 后端删除结点 public Object removeLast(){ if(isEmpty()){ System.out.println("队列为空"); } DoubleNode first = trailer.getPrev(); DoubleNode second = first.getPrev(); // 要删除结点的值 Object value = first.getVal(); // 将尾结点的 prev 指向要删除的前驱结点 second,同时将 second 的后继结点指向尾结点 trailer.setPrev(second); second.setNext(trailer); // 更新规模 size--; return value; }}
总结
本文从单向链表和双向链表的结构定义出发,然后又分别介绍了如何基于单向链表实现堆和栈,最后则是对双向链表的增删改查进行了总结。对于文中有疏漏的地方,欢迎评论留言。如果你觉得文章对你有所帮助,那就点个赞再走吧!
转载地址:https://cunyu1943.blog.csdn.net/article/details/107157291 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月25日 03时53分57秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
12月8日 RCEA - RT-Thread能力认证考试考前通知
2019-04-29
论坛热贴 | RT-Thread音频驱动开发(一)
2019-04-29
基于 Keil MDK 移植 RT-Thread Nano
2019-04-29
【报名截至今晚】12月14日深圳嵌入式与音频开发专题会议预告
2019-04-29
移植 RT-Thread Nano 到 RISC-V
2019-04-29
软件包应用分享|基于RT-Thread的百度语音识别(二)
2019-04-29
在 RT-Thread Nano 上添加控制台与 FinSH
2019-04-29
一站式开发工具:RT-Thread Studio 正式发布
2019-04-29
留言有礼|谢谢你悄悄点了小星星,让我们跃居GitHub RTOS Star榜第一
2019-04-29
功能更新!C 函数也能在 MicroPython 中被调用啦
2019-04-29
东软载波携ES32+RT-Thread走进海尔集团
2019-04-29
今晚8点直播预告:RT-Thread Studio等相关主题答疑
2019-04-29
物联网 20 年简史大揭秘!
2019-04-29
开源项目|RT-Thread 软件包应用作品:水墨屏桌面台历
2019-04-29
珠联璧合!基于i.MX RT和RT-Thread的物联网云接入方案
2019-04-29
基于RTT-MicroPython制作自带BGM的新型肺炎晴雨表
2019-04-29
开源项目|RT-Thread 软件包应用作品:小闹钟
2019-04-29
在 RT-Thread Studio 上使用 RT-Thread Nano
2019-04-29