线性表的链式存储——链表

news/2024/11/28 3:27:34/

目录

1.概念

2.链表

2.1 单链表概念及结构

2.2双链表的概念及结构

2.3 循环链表 

3.链表的具体使用

4.自己实现链表及方法：

双链表：

单链表：

1.概念

        链式存储是常用的动态存储方式，相对于顺序表，可以更好的任意插入与删除，而采用链式存储的结构叫做链表。

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

        从链接方式的角度：链表分为单链表、双链表及循环链表；

        从实现方式的角度：链表分为动态链表和静态链表；

2.链表

2.1 单链表概念及结构

 概念：

        单链表是通过一个一个结点进行连接，而链表并不像顺序表一样存储的是一组地址连续的存储单元，而是非连续的。因此，链表中的结点不仅需要存储自己的数据元素值（数据域），还需要存储下一个结点的地址（指针域）。

 结构：

        

        单链表的每个结点的地址都存储在其前驱结点的指针域中，因此第一个结点无前驱，这个时候我们可以设置一个头指针Head指向第一个结点。而最后一个结点后面没有结点，所以最后一个结点指针域为空（Null）。

 单链表结构：

2.2双链表的概念及结构

概念：

        每个结点相对与单链表多了一个指针域，其它与单链表基本相同。

结构：

2.3 循环链表 

概念：

        循环链表是建立在单链表和双链表的基础上，将头尾相连，形成一个环，这就是循环链表，可分为：循环单链表、循环双链表。

 

3.链表的具体使用

方法解释
add（E e）尾插 e

add（int i, E e） 

把e插在i位置
addAll(Collection<? extends E> c)尾插c
addFirst（E e）头插e
remove（int i）删除i坐标元素
remove（int i）删除i坐标元素
get（int i）获得i坐标元素
set（int i ， E e）将i坐标元素换为e
clear（）清空
contains（object o ）判定o是否存在
indexOf（object  o）返回第一个o所在位置的下标
lastIndexOf（object o）返回最后一个o下标
subList(int f, int t)截取f坐标到t坐标list

 代码实现：

public class Test1 {public static void main(String[] args) {System.out.println(list.add(1));//尾插1，Booleanlist.addFirst(2);//头插2System.out.println(list);list.addLast(3);//尾插3System.out.println(list);list.add(1,4);//1坐标插入4System.out.println(list);list.remove(2);//删除2坐标元素System.out.println(list);System.out.println(list.get(2));//获得2坐标元素System.out.println(list);list.set(1,3);//将1坐标元素改为3System.out.println(list);System.out.println(list.contains(3));//是否含5System.out.println(list.contains(6));//是否含6System.out.println(list.indexOf(3));//第一个3的下标System.out.println(list.lastIndexOf(3));//最后一个3的下标System.out.println(list.subList(0,1));//截取[0,1)的list，前闭后开System.out.println(list.isEmpty());//list中是否有元素list.clear();//清空System.out.println(list.isEmpty());}
}

运行结果：

true
[2, 1]
[2, 1, 3]
[2, 4, 1, 3]
[2, 4, 3]
3
[2, 4, 3]
[2, 3, 3]
true
false
1
2
[2]
false
true

4.自己实现链表及方法：

注意：

        上面这些方法的实现，我们可以直接用，但是我们也可以创建自己的链表，实现自己的方法，让我们更好的理解，提升我们的代码能力。

        代码的实现我放在了下面，但是最好自己实现一遍。

双链表：

public class MyLinkedList {static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//头插法public void addFirst(int data){ListNode listNode = new ListNode(data);if (head == null){head = listNode;last = listNode;}else{head.prev = listNode;listNode.next = head;head = listNode;}}//尾插法public void addLast(int data){ListNode listNode = new ListNode(data);if(last == null){last = listNode;head = listNode;}else{last.next = listNode;listNode.prev = last;last = listNode;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){ListNode listNode = new ListNode(data);if(index < 0 || index > size()){System.out.println("不合法");return;}if(index == 0){addFirst(data);return;}if (index == size()){addLast(data);return;}ListNode cur = head;for (int i = 0; i < index; i++) {cur = cur.next;}listNode.next = cur;cur.prev.next = listNode;listNode.prev = cur.prev;cur.prev = listNode;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null){if(cur.val == key){return true;}}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;while (cur != null){if(cur.val == key){if(cur == head){head = head.next;}else{if (cur.next == null) {cur.prev.next = null;last = cur.prev;}else{cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;}else{cur = cur.next;}}System.out.println("没有这个节点");}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur = head;while (cur != null){if(cur.val == key){if(cur == head){head = head.next;}else{if (cur.next == null) {cur.prev.next = null;last = cur.prev;}else{cur.prev.next = cur.next;cur.next.prev = cur.prev;}}}cur = cur.next;}}//得到单链表的长度public int size(){int count = 0;ListNode cur = head;while (cur != null){count++;cur = cur.next;}return count;}public void display(){ListNode cur = head;while (cur != null){System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}public void clear(){head = null;}
}

单链表：

public class SingleLinkedList {class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public void createNode(){ListNode listNode1 = new ListNode(12);ListNode listNode2 = new ListNode(23);ListNode listNode3 = new ListNode(34);ListNode listNode4 = new ListNode(45);ListNode listNode5 = new ListNode(45);head = listNode1;listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;}public ListNode head;//打印public void show(){ListNode cur = head;for (int i = 0; i < size(); i++) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//长度public int size(){ListNode cur = head;int count = 0;while(cur != null){cur = cur.next;count++;}return count;}//查找public boolean contains(int key){ListNode cur = head;if(cur == null){return false;}while (cur.val != key){if(cur.next == null){return false;}cur = cur.next;}return true;}//头插public void addFirst(int data){ListNode newNode = new ListNode(data);newNode.next = head;head = newNode;}//尾插public void addLast(int data){ListNode newNode = new ListNode(data);ListNode cur = head;while (cur.next != null){cur = cur.next;}cur.next = newNode;}//随意插public void addIndex(int index,int data){ListNode cur = head;ListNode newNode = new ListNode(data);if(index == 0){addFirst(data);return;}if(index < 0 || index > size() || cur == null){throw new IndexOutOfBounds("数组不合法，越界: " + index);}if(index == size()){addLast(data);return;}for (int i = 1; i < index; i++) {cur = cur.next;}newNode.next = cur.next;cur.next = newNode;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;ListNode pver = head;if(cur == null){System.out.println("链表无节点");return;}if(cur.val == key){head = head.next;}while(cur.val != key){if(cur.next == null){System.out.println("无此节点");return;}pver = cur;cur = cur.next;}if(cur.val == key){pver.next = cur.next;return;}}//删除所有值为key的节点public void removeAllKey(int key){if(head == null) {return;}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 void clear(){head = null;}
}

 


http://www.ppmy.cn/news/41814.html

相关文章

猿辅导学员入选国家队，竞赛老师成为“最强辅助”

猿辅导学员入选国家队，竞赛老师成为“最强辅助”

3月31日&#xff0c;国际数学奥林匹克竞赛&#xff08;IMO&#xff09;国家队名单正式出炉&#xff0c;猿辅导学员王淳稷、孙启傲分别以第一名和第二名的成绩位列其中&#xff0c;今年7月&#xff0c;他们将出征日本&#xff0c;代表中国参赛&#xff0c;为国争光。 自2020年以…
阅读更多...
ChatGPT 指令大全

ChatGPT 指令大全

1、写报告 报告开头 我现在正在 报告的情境与目的 。我的简报主题是 主题 &#xff0c;请提供 数字 种开头方式&#xff0c;要简单到 目标族群 能听懂&#xff0c;同时要足够能吸引人&#xff0c;让他们愿意专心听下去。 &#x1f330; 我现在正在修台大的简报课&#xff0c;其…
阅读更多...
2023年全国最新高校辅导员精选真题及答案49

2023年全国最新高校辅导员精选真题及答案49

百分百题库提供高校辅导员考试试题、辅导员考试预测题、高校辅导员考试真题、辅导员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 76.气质就是我们平常所说的脾气秉性。 答案&#xff1a;正确 77.社会心理通常是通过社会…
阅读更多...
当我开始学习人工智能：知识表示方法

当我开始学习人工智能：知识表示方法

加油加油&#xff0c;五一前复习玩&#xff0c;五一就可以出去玩啦 一、状态空间法&#xff08;State Space Representation&#xff09; 问题求解技术主要是两个方面 问题的表示求解的方法 状态空间法 状态算符状态空间方法 1.1 问题状态描述 定义 状态&#xff1a;描述某类不…
阅读更多...
每天一道大厂SQL题【Day20】华泰证券真题实战(二)表转置

每天一道大厂SQL题【Day20】华泰证券真题实战(二)表转置

每天一道大厂SQL题【Day20】华泰证券真题实战(二) 大家好&#xff0c;我是Maynor。相信大家和我一样&#xff0c;都有一个大厂梦&#xff0c;作为一名资深大数据选手&#xff0c;深知SQL重要性&#xff0c;接下来我准备用100天时间&#xff0c;基于大数据岗面试中的经典SQL题&…
阅读更多...
【MATLAB图像处理实用案例详解（9）】——基于最大类间方差遗传算法的道路分割

【MATLAB图像处理实用案例详解（9）】——基于最大类间方差遗传算法的道路分割

目录一、最大类间方差遗传算法二、代码示例一、最大类间方差遗传算法 最大类间方差的求解过程&#xff0c;就是在解空间中查找到一个最优的解&#xff0c;使得其方差最大&#xff0c;而遗传算法能非线性快速查找最优解k*及最大的方差&#xff0c;其步骤如下&#xff1a; ①为了…
阅读更多...
《2023金融科技·校园招聘白皮书》新鲜出炉|牛客独家

《2023金融科技·校园招聘白皮书》新鲜出炉|牛客独家

数智创新时代&#xff0c;科技人才为先。 眼下&#xff0c;在建设“数字中国”的时代背景下&#xff0c;金融行业全面数智化转型已箭在弦上。政策端&#xff0c;金融行业为中共中央、国务院印发《数字中国建设整体布局规划》的7大重点行业之一。 资本端&#xff0c;仅2022年三…
阅读更多...
手把手教你安装Visual Studio 2019（史上最全）

手把手教你安装Visual Studio 2019（史上最全）

前言： 本文是以Visual Studio Community 2019为例子，介绍如何在微软官网下载Visual Studio Community 2019并安装.net桌面开发程序环境（主要是winform开发环境）。 下载请点击这里Visual Studio Community 2019下载，然后点击下图的箭头的DownLoad下载，要注意的是下载时要…
阅读更多...
最新文章

Copyright @ 2022~2023