🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧上一篇文章：从顺序表到ArrayList类🎈🎈🎈🎈🎈
文章目录
- 1.前言
- 2.链表
- 2.1 链表的概念及结构
- 2.2链表的组合
- 2.3链表的实现
- 2.4LinkedList的模拟实现
- 3.ArrayList和LinkedList的区别
1.前言
上一篇文章我们了解ArrayList表的使用，并且模拟了ArrayList表，通过数组的方式来存储数据单元。其底层是一块连续储存的空间，这时候我们发现当我们去插入数据或者删除数据的时候，需要将前后的数据整体向前移动或者向后移动。因此ArrayList是不能满足我们的需求。接下来我们可以来看看即将要学的LinkedList表。
2.链表
2.1 链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。结构像我们平时坐的交通工具火车一样，一节一节的，并不是按一定的顺序链接的，车厢可以随意链接，链表也是这样的。
注意：
1.从图中可以看出，链式结构不一定在物理上是连续的空间，但在逻辑上是连续的空间。
2.现实中的结点一般都是在堆上申请出来的。
3。在堆上申请的空间，是按定一定的规则来分配的，两次申请的空间可能是连续的空间，也有可能不是连续的空间。
2.2链表的组合
在现实当中有很多种的链表，有分单向和双向，带头和不带头，循环和不循环，总共有八种组合方式：
1.单向带头循环
2.单向带头不循环
3.单向不带头循环
4.单向不带头不循环
5.双向带头循环
6.双向带头不循环
7.双向不带头循环
8.双向不带头不循环
这么多种类型的链表，我们只了解两种单向不带头不循环和双向不带头不循环。
单向不带头不循环：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
双向不带头不循环：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2.3链表的实现
2.3.1头插法
public void addFirst(int data) { ListNode node = new ListNode(data); //如果没有节点,直接将head标记放在要插的节点上，作为第一个首节点 if(head == null) { this.head = node; } else { //先绑定，再移标记引用变量 node.next = this.head; this.head = node; } }2.3.2尾插法
public void addLast(int data) { ListNode node = new ListNode(data); //如果没有节点,直接将head标记放在要插的节点上，作为第一个尾节点 if(head == null) { this.head = node; } else { ListNode cur = head; while(cur.next != null) { cur = cur.next; } cur.next = node; } }2.3.3任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) { //判断index是否合法 if(index < 0 || index > size()) { throw new IndexException("坐标"+index+":位置不合法"); } ListNode node = new ListNode(data); //1.如果从头插入，直接头插法 if(index == 0) { addFirst(data); } //2.从中间插 ListNode cur = searchPrevIndex(index); node.next = cur.next; cur.next = node; } //创建一个找前驱的方法 private ListNode searchPrevIndex(int index) { ListNode cur = head; int count = 0; while(count < index-1) { cur = cur.next; count++; } return cur; }2.3.4查找是否包含关键字key是否在单链表当中
public boolean contains(int key) { ListNode cur = head; while(cur != null) { if(key == cur.value) { return true; } cur = cur.next; } return false; }2.3.5删除第一次出现关键字为key的节点
public void remove(int key) { //删除头节点 if(head.value == key) { head = head.next; return; } //1.找到要删除key的前驱 ListNode cur = searchPrevKey(key); if(cur == null) { return;//没有你要删除的key } //2.定义一个标记curNext ListNode curNext = cur.next; //3.删除key cur.next = curNext.next; } private ListNode searchPrevKey(int key) { ListNode cur = head; while(cur.next != null) { if(cur.next.value == key) { return cur; } else { cur = cur.next; } } return null; }2.3.6删除所有值为key的节点(非循环方法)
public void removeAllKeye(int key) { ListNode prev = head; ListNode cur = head.next; while (cur != null) { if(cur.value == key) { prev.next = cur.next; cur = cur.next; }else { prev = cur; cur = cur.next; } } //删除头节点 if(head.value == key) { head = head.next; } }2.3.7得到单链表的长度
public int size() { ListNode cur =head; int count = 0; while(cur != null) { cur = cur.next; count++; } return count; }2.3.8清空链表
public void clear() { head = null; } }2.4LinkedList的模拟实现
** 2.4。1头插法**
public void addFirst(int data) { ListNode node = new ListNode(data); //如果链表为空 if(head == null) { head = node; last = node; } else { //链表不为空 node.next = head; head.prev = node; node.prev = null; head = node; } }** 2.4。2尾插法**
public void addLast(int data) { ListNode node = new ListNode(data); //如果链表为空 if(head == null) { head = node; last = node; } else { //链表不为空 last.next = node; node.prev = last; node.next = null; last = node; } }** 2.4.3任意位置插入,第一个数据节点为0号下标**
public void addIndex(int index, int data) { //先判断index合不合法 if(index<0 || index >size()) { throw new IndexException("位置不合法:"+index); } //1.从头插入，头插法 if(index == 0) { addFirst(data); return; } //2.从尾插，尾插法 if(index == size()) { addLast(data); return; } //3.从中间插 //找要插入的位置 ListNode cur = findAddIndex(index); ListNode node = new ListNode(data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; } private ListNode findAddIndex(int index) { ListNode cur = head; while(index != 0) { cur = cur.next; index--; } return cur; }** 2.4.4查找是否包含关键字key是否在单链表当中**
public boolean contains(int key) { ListNode cur = head; while(cur != null) { if(cur.value == key) { return true; } else { cur = cur.next; } } return false; }** 2.4.5删除第一次出现关键字为key的节点**
public void remove(int key) { ListNode cur = head; while (cur != null) { if(cur.value == key) { if(cur == head) { //删除头节点 head = head.next; if(head != null) { head.prev = null; }else { //只有一个节点 且是需要删除的节点 last = null; } }else { //删除中间节点 if(cur.next != null) { cur.next.prev = cur.prev; cur.prev.next = cur.next; }else { //删除尾巴节点 cur.prev.next = cur.next; last = last.prev; } } return; } cur = cur.next; } }** 2.4.6删除所有值为key的节点**
public void removeAllKeye(int key) { ListNode cur = head; while (cur != null) { if(cur.value == key) { if(cur == head) { head = head.next; if(head != null) { head.prev = null; }else { //只有一个节点 且是需要删除的节点 last = null; } }else { //删除中间节点 if(cur.next != null) { cur.next.prev = cur.prev; cur.prev.next = cur.next; }else { //删除尾巴节点 cur.prev.next = cur.next; last = last.prev; } } } cur = cur.next; } }** 2.4.7得到双链表的长度**
public int size() { ListNode cur = head; int count = 0; while(cur != null) { count++; cur = cur.next; } return count; }** 2.4.8清除链表**
public void clear() { head =null; last =null; }3.ArrayList和LinkedList的区别
结尾：
希望大家可以给我点点关注，点点赞，你们的支持就是我的最大鼓励。🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹
- 3.ArrayList和LinkedList的区别