数据结构之链表
2023-03-09 22:24:11 时间
数组的两大缺点：
1。若改变数组的大小就要创建一个新的数组，并需要从原数组复制所有的数据到新的数组
2。数组元素在内存中依次顺序存储，这意味着向数组插入一项要移动数组中的其他元素
因此，我们使用链式结构，链式结构是存储数据的结点以及指向其他节点的指针的集合。如此一来，节点可以位于内存的任意位置，而且从一个节点到另一个节点的传递可以通过在结构中存储节点间引用来实现。
一。单向链表
1。链表：
如果一个节点包含指向另一个节点的数据值，那么多个节点可以连接成一串，只通过一个变量访问整个节点序列，这样的节点序列称为链表（linked list）
2。单向链表：
如果每个节点仅包含其指向后继节点的引用，这样的链表称为单向链表。
一个整型单向链表的实现：
package com.sohu.blog.denns_zane.list;
/** 
* @author dennis * @Description 整型单向链表节点
*/ public class IntSLLNode {
public int info; // 用户信息 public IntSLLNode next; // 下一个节点，自引用 
/** 
* @param info * @param next
*/ public IntSLLNode( int info, IntSLLNode next) { this .info = info; this .next = next; } /** * @param info */ public IntSLLNode( int info) { this (info, null ); } } /** * */ package com.sohu.blog.denns_zane.list; /** * @author dennis * desc: 整型单向链表 */ public class IntSLList { protected IntSLLNode head, tail; public IntSLList() { head = tail = null ; } public boolean isEmpty() { return head == null ; } /** * @description 增加新节点，并设置它的next为原head * @param el */ public void addToHead( int el) { head = new IntSLLNode(el, head); if (tail == null ) tail = head; } /** * @description 增加新节点，并设置原tail的next为新节点 * @param el */ public void addToTail( int el) { if ( ! isEmpty()) { tail.next = new IntSLLNode(el); tail = tail.next; } else { head = tail = new IntSLLNode(el); } } public int deleteFromHead() { if (head == null ) throw new NullPointerException(); int el = head.info; if (head == tail) head = tail = null ; else head = head.next; return el; } public int deleteFromTail() { if (head == null ) throw new NullPointerException(); int el = tail.info; if (head == tail) head = tail = null ; else { IntSLLNode temp; for (temp = head; temp.next != null && temp.next != tail; temp = temp.next) tail = temp; System.out.println(tail.info); tail.next = null ; } return el; } public void printAll() { for (IntSLLNode temp = head; temp != null ; temp = temp.next) System.out.print(temp.info + " " ); } public boolean isInList( int el) { for (IntSLLNode temp = head; temp != null ; temp = temp.next) { if (temp.info == el) return true ; } return false ; } /** * @param el */ public void delete( int el) { if ( ! isEmpty()) { if (head == tail && head.info == el) head = tail = null ; else if (head.info == el) head = head.next; else { IntSLLNode pred, temp; // pred为找的节点的前一节点，temp即为找到的节点 for (pred = head, temp = head.next; temp != null ; pred = pred.next, temp = temp.next) { if (temp.info == el) { pred.next = temp.next; // 前一节点的next设置为当前节点的next if (temp == tail) tail = pred; } } } } } } 二。双向链表
一个整型双向链表的实现：
/** * */package com.sohu.blog.denns_zane.list;/** * @author dennis desc:双向链表节点 */public class IntDLLNode { public int info; public IntDLLNode prev, next; /** * @param info * @param prev * @param next */ public IntDLLNode(int info, IntDLLNode next, IntDLLNode prev) { super(); this.info = info; this.prev = prev; this.next = next; } public IntDLLNode(int info) { this(info, null, null); }}/** * */package com.sohu.blog.denns_zane.list;/** * @author dennis * */public class IntDLList { private IntDLLNode head, tail; public IntDLList() { head = tail = null; } public boolean isEmpty() { return head == null; } public void addToHead(int el) { if (head == null) head = new IntDLLNode(el); else { head = new IntDLLNode(el, head, null); head.next.prev = head; } if (tail == null) tail = head; } public void addToTail(int el) { if (!isEmpty()) { tail = new IntDLLNode(el, null, tail); tail.prev.next = tail; } else head = tail = new IntDLLNode(el); } public int removeFromTail() { if (head == null) throw new NullPointerException(); int el = tail.info; if (head == tail) head = tail = null; else { tail = tail.prev; tail.next = null; } return el; } public int removeFromHead() { if (head == null) throw new NullPointerException(); int el = head.info; if (head == tail) head = tail = null; else { head = head.next; head.prev = null; } return el; } public boolean isInList(int el) { if (head == null) return false; IntDLLNode temp; for (temp = head; temp != null; temp = temp.next) { if (temp.info == el) { return true; } } return false; } public void delete(int el) { if (head == null) throw new NullPointerException(); IntDLLNode temp; for (temp = head; temp != null; temp = temp.next) { if (temp.info == el) { if (temp == head) { head.next.prev = null; head = head.next; } else temp.prev.next = temp.next; } } } public void printAll() { IntDLLNode temp; for (temp = head; temp != null; temp = temp.next) { System.out.print(temp.info + " "); } System.out.println(); }}
三。跳转表，循环表，自组织表（略）
四。结论
1。需要随机访问某元素，数组更为合适
2。需要动态分配内存，经常改变结构，链表更为合适
3。相比于链表，数组更为节约空间。毕竟链表节点还需要保存一个或者两个引用
文章转自庄周梦蝶 ，原文发布时间5.17
相关文章
- React入门一：React简介及基本使用 ｜ 8月更文挑战
- React入门二：React脚手架的使用 ｜ 8月更文挑战
- React入门三： JSX | 8月更文挑战
- 5why分析总是起不了作用？原因在这里 - 优思学院
- 《汽车软件全景图（2022年）》
- ES6 字符串新增方法
- Mac无法读取硬盘
- 爬取当当网评论
- Ant Design Umi 项目创建
- React DOM Diff算法
- 深入浅出ES6的迭代器
- MQTT QoS 0, 1, 2 介绍
- AI 2023软件下载和安装教程
- AI 2022软件下载和安装教程
- AI 2021软件下载和安装教程
- nvm 和 nrm
- AI 2020软件下载和安装教程
- AI 2019软件下载和安装教程
- Ajax 如何解决跨域问题
- 小程序中如何添加用户隐私保护指引