前言
在前面我们已经学习了关于顺序表ArrayList的一些基本操作。通过源码知道，ArrayList底层使用数组来存储元素，由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构
一、链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的
注意：
1.链式结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续，也可能不连续
链表的结构有8种样式：
- 单向带头循坏、单向带头非循坏、单向不带头循坏、单向不带头非循坏
- 双向带头循坏、双向带头非循坏、双向不带头循坏、双向不带头非循坏
这里我们主要学习以下两中结构：
单向不带头非循坏
LinkedList底层使用的就是双向不带头非循坏
二、单向不带头非循坏链表的实现
创建一个类：
public class MySingleList { static class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; } } //链表的头节点 public ListNode head; }
2.1打印链表
不带参数的打印
public void display() { ListNode cur = head; if(cur != null) {//遍历完所以节点 System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); }
带参数的打印
public void display(ListNode newHead) { ListNode cur = newHead; if(cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); }
2.2求链表的长度
public int size(){ ListNode cur = head; int count = 0; while (cur != null) { count++; cur = cur.next; } return count; }
2.3头插法
public void addFirst(int data){ ListNode node = new ListNode(data); node.next = head; head = node; }
2.4尾插法
public void addLast(int data){ ListNode node = new ListNode(data); if(head == null) { head = node; }else { ListNode cur = head; while (cur.next != null) {//走到最后一个节点的位置 cur = cur.next; } cur.next = node; } }
2.5任意位置插入
在任意位置插入时我们要判断该位置是否合法，不合法的时候要抛一个异常
public void addIndex(int index,int data){ if(index < 0 || index > size()) { throw new IndexException("index位置不合法："+index); } ListNode node = new ListNode(data); if(head == null) { head = node; return; } if(index == 0) { addFirst(data); return; } if(index == size()) { addLast(data); return; } //中间插入 ListNode cur = serchIndex(index); node.next = cur.next; cur.next = node; }
找要添加节点位置的前一个节点
public ListNode serchIndex(int index) { ListNode cur = head; int count = 0; while (count != index-1) { cur = cur.next; count++; } return cur; }
2.6查找是否包含某个元素的节点
遍历这个链表找是否与这个元素相同
public boolean contains(int key){ ListNode cur = head; while (cur != null) { if(cur.val == key) { return true; } cur = cur.next; } return false; }
2.7删除第一次出现这个元素的节点
public void remove(int key){ if(head == null) { return; } if(head.val == key) { head = head.next; return; } ListNode cur = findKey(key); if(cur == null) { return;//没有要删除的元素 } ListNode del = cur.next; cur.next = del.next; }
要删除节点的前一个节点
public ListNode findKey(int key) { ListNode cur = head; while (cur.next != null) { if(cur.next.val == key) { return cur; }else { cur = cur.next; } } return null; }
2.8删除包含这个元素的所以节点
public void removeAllKey(int key){ if(head == null) { return; } ListNode prev = head; ListNode cur = head.next; 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; } }
2.9清空链表
清空链表只需要把头节点置为空
public void clear() { head = null; }
单向链表的测试
public class Test { public static void main(String[] args) { MySingleList list = new MySingleList(); list.addLast(30);//尾插 list.addLast(20); list.addLast(30); list.addLast(40); list.addLast(50); list.addFirst(100);//头插 list.addIndex(2,15);//任意位置插入 list.display(); System.out.println("*"); System.out.println(list.contains(20));//查看是否包含某个节点 System.out.println("*"); System.out.println(list.size());//求链表长度 System.out.println("*"); list.remove(30);//删除第一个出现的节点 list.display(); list.removeAllKey(30);//删除包含这个元素的所以节点 System.out.println("*"); list.display(); System.out.println("*"); list.clear();//清空链表 list.display(); } }
三、双向不带头非循坏链表的实现
创建一个类：
static class ListNode { public int val; public ListNode next; public ListNode prev; public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last; }
3.1打印双向链表
public void display(){ ListNode cur = head; while (cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); }
3.2求双向链表的长度
public int size(){ int count = 0; ListNode cur = head; while (cur != null) { count++; cur = cur.next; } return count; }
3.3头插法
public void addFist(int data) { ListNode node = new ListNode(data); if(head == null) {//一个节点都没有的情况 head = node; last = node; }else { node.next = head; head.prev = node; head = node; } }
3.4尾插法
public void addLast(int data) { ListNode node = new ListNode(data); if(head == null) {//一个节点都没有的情况 head = node; last = node; }else { last.next = node; node.prev = last; last = node; } }
3.5任意位置插入
这里的插入与单向链表一样也需要判断该位置的合法性，不合法时抛一个异常
public void addIndex(int index,int data) { if(index < 0 || index > size()) { throw new IndexException("双向链表中index的位置不合法："+index); } if(index == 0) { addFist(data); } if(index == size()) { addLast(data); } ListNode cur = findIndex(index); ListNode node = new ListNode(data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; }
要添加节点的位置
public ListNode findIndex(int index) { ListNode cur = head; if(index != 0) { cur = cur.next; index --; } return cur; }
3.6查找是否包含某个元素的节点
public boolean contains(int key){ ListNode cur = head; while (cur != null) { if(cur.val == key) { return true; } cur = cur.next; } return false; }
3.7删除第一次出现这个元素的节点
因为数据结构是一门逻辑性非常严谨的学科，所以这里的删除需要考虑多种因素
public void remove(int key){ ListNode cur = head; while (cur != null) { if(cur.val == 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; } }
3.7删除包含这个元素的所有节点
public void remove(int key){ ListNode cur = head; while (cur != null) { if(cur.val == 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; } }
3.9清空双向链表
public void clear(){ ListNode cur = head; while (cur != null) { ListNode curNext = cur.next; cur.prev = null; cur.next = null; cur = cur.next; } head = null;//头节点置空 last = null;//尾巴节点置空 }
双向链表的测试
public class Test { public static void main(String[] args) { MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addLast(12);//尾插法 myLinkedList.addLast(45); myLinkedList.addLast(34); myLinkedList.addLast(45); myLinkedList.addFist(56);//头插法 myLinkedList.addIndex(2,15);//任意位置插入 myLinkedList.display(); System.out.println(myLinkedList.size());//求双向链表的长度 System.out.println(""); System.out.println(myLinkedList.contains(23));//查找是否包含某个元素的节点 System.out.println(""); myLinkedList.remove(45);//删除第一次出现这个元素的节点 myLinkedList.display(); System.out.println(""); myLinkedList.removeAllKey(45);//删除包含这个元素的所以节点 myLinkedList.display(); System.out.println(""); myLinkedList.clear();//清空链表 myLinkedList.display(); } }
LinkedList的遍历方式
关于LinkedList的遍历方式有四种：
public class Test { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(4); System.out.println(list); //for循坏遍历 for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i)+" "); } System.out.println(); System.out.println("*"); java链表基础算法 //foreach遍历 for (int m : list) { System.out.print(m +" "); } System.out.println(); System.out.println("*"); //使用迭代器——正向遍历 ListIterator<Integer> it = list.listIterator(); while (it.hasNext()) { System.out.print(it.next()+" "); } System.out.println(); System.out.println("*"); //使用迭代器——反向遍历 ListIterator<Integer> it2 = list.listIterator(list.size()); while (it2.hasPrevious()) { System.out.print(it2.previous()+" "); } System.out.println(); } }
四、ArrayList和LinkedList的区别
1.ArrayList在物理上是连续的，LinkedList在逻辑上连续，但在物理上不一定连续
2.ArrayList和LinkedList是两种不同的数据结构。ArrayList是基于动态数组的，而LinkedList则是基于链表的
3.当需要随机访问元素（如get和set操作）时，ArrayList效率更高，因为LinkedList需要逐个查找。但当进行数据的增加和删除操作（如add和remove操作）时，LinkedList效率更高，因为ArrayList在进行这些操作时需要移动大量数据
4.ArrayList需要手动设置固定大小的容量，使用方便但自由性低；而LinkedList能够随数据量变化而动态调整，自由性较高但使用较为复杂
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/2813.html