目录
一.什么是链表?
链表的类型
链表的特点
使用场景:
二.单向链表的实现:
首先创建节点类以及对应的构造方法:
然后创造头结点(哨兵结点),方便找到固定的位置来对链表进行操作:
最后列出简单的对链表的增删改查操作:
三.双向链表的实现:
首先创建节点类以及对应的构造方法:
然后创建头尾哨兵,便于在两哨兵中间插入元素以及双向链表的操作:
随后创建这个双向链表的构造方法:
最后实现对双向链表的操作:
四.双向循环链表的实现:
首先创造哨兵结点以及其构造函数:
随后实现对双向循环链表的操作:
一.什么是链表?
链表(Linked List) 是一种线性数据结构,其中元素称为节点(Node)。每个节点包含两个部分:
- 数据域(data):存储节点的值。
- 指针域(next):存储下一个节点的地址(或引用),指向链表中的下一个节点。
与数组不同,链表的元素在内存中不一定连续存储。链表的灵活性在于可以动态调整大小,因为元素的插入和删除操作不涉及移动其他元素。
链表的类型
- 单向链表(Singly Linked List):每个节点只有一个指针指向下一个节点。
- 双向链表(Doubly Linked List):每个节点有两个指针,一个指向前一个节点,一个指向下一个节点。
- 循环链表(Circular Linked List):链表的最后一个节点指向第一个节点,形成一个闭环。
链表的特点
- 动态大小:与数组不同,链表不需要在创建时指定大小。
- 插入和删除效率高:特别是在中间或开头插入和删除操作,链表的效率要高于数组。
- 随机访问效率低:由于链表节点不连续存储,无法像数组那样通过索引直接访问元素。
使用场景:
- 频繁插入和删除:在需要频繁在中间插入和删除元素的场景,链表表现较好,因为插入和删除操作的时间复杂度为 O(1),不需要像数组那样移动元素。
- 动态大小:当不确定数据的大小时,链表比数组更适合,因为它可以根据需要动态调整大小。
- 内存碎片化:链表不要求内存连续分配,适合在内存较为分散的场景。
二.单向链表的实现:
每个节点只有一个指针指向下一个节点。
首先创建节点类以及对应的构造方法:
//结点类
//做成内部类,以此来对外隐藏
private static class Node {int value; // 值Node next; // 下一个结点指针public Node(int value, Node next) {this.value = value;this.next = next;}
}
然后创造头结点(哨兵结点),方便找到固定的位置来对链表进行操作:
private Node head = new Node(666,null);
最后列出简单的对链表的增删改查操作:
package LinkListStudy;import java.util.Iterator;
import java.util.function.Consumer;public class SinglyLinkedListSentinel implements Iterable<Integer> {//头指针
// private Node head = null;//哨兵结点private Node head = new Node(666,null);//迭代器遍历链表@Overridepublic Iterator<Integer> iterator(){//匿名内部类 -> 带名字的内部类return new Iterator<>() {//头结点为哨兵结点,需要从下一个结点开始Node pointer = head.next;@Overridepublic boolean hasNext() {return pointer != null;}@Overridepublic Integer next() {int v = pointer.value;pointer = pointer.next;return v;}};}//结点类//做成内部类,以此来对外隐藏private static class Node {int value; // 值Node next; // 下一个结点指针public Node(int value, Node next) {this.value = value;this.next = next;}}//向链表中添加元素public void addFirst(int value) {//链表为空
// head = new Node(value, null);//链表非空
// head = new Node(value, head);insert(0,value);}//使用函数式接口遍历链表public void loop1(Consumer<Integer> consumer) {Node pointer = head;while (pointer != null) {consumer.accept(pointer.value);//consumer接受数据pointer = pointer.next;//指针移动}}public void loop2(Consumer<Integer> consumer) {for (Node pointer = head.next; pointer != null; pointer = pointer.next) {consumer.accept(pointer.value);}}//寻尾部结点对象public Node findLast(){for(Node pointer = head.next;; pointer = pointer.next) {if(pointer.next == null){return pointer;}}}//尾插法public void addLast(Integer value) {Node last = findLast();//插入last.next = new Node(value, null);}//获取结点索引值public Node findNode(int index){//哨兵为 -1 索引int i = -1;for(Node pointer = head; pointer != null; pointer = pointer.next,i++) {if(i == index){return pointer;}}return null;}//返回某一位置索引值public int get(int index) throws IllegalArgumentException{Node node = findNode(index);if(node == null) {throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index));}return node.value;}//向索引位置插入public void insert(int index, int value) throws IllegalArgumentException{Node node = findNode(index - 1);if(node == null){throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));}node.next = new Node(value, node.next);}//删除第一个节点public void removeFirst() throws IllegalArgumentException{
// if(head == null){
// throw new IllegalArgumentException(String.format("Index %d 不合法%n ", 0));
// }
// head = head.next;remove(0);}//删除指定结点索引元素public Node remove(int index){Node node = findNode(index - 1);if(node == null){throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));}Node removed = node.next;if(removed == null){throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));}node.next = node.next.next;return removed;}//递归遍历private void recursion(Node curr){if(curr == null){return ;}System.out.println(curr.value);recursion(curr.next);}public void loop3(){recursion(head);}
}
三.双向链表的实现:
每个节点有两个指针,一个指向前一个节点,一个指向下一个节点。
首先创建节点类以及对应的构造方法:
static class Node{int value;//值Node next;//下一个结点Node prev;//上一个结点public Node(Node prev, int value , Node next) {this.prev = prev;this.value = value;this.next = next;}
}
然后创建头尾哨兵,便于在两哨兵中间插入元素以及双向链表的操作:
private Node head;//头哨兵
private Node tail;//尾哨兵
随后创建这个双向链表的构造方法:
//头 <=> 尾
public DoubleLinkedListSentinel() {head = new Node(null, 0, null);tail = new Node(null, 0, null);head.next = tail;tail.prev = head;
}
最后实现对双向链表的操作:
package LinkListStudy;import java.util.Iterator;public class DoubleLinkedListSentinel implements Iterable<Integer>{static class Node{int value;//值Node next;//下一个结点Node prev;//上一个结点public Node(Node prev, int value , Node next) {this.prev = prev;this.value = value;this.next = next;}}//哨兵private Node head;//头哨兵private Node tail;//尾哨兵//头 <=> 尾public DoubleLinkedListSentinel() {head = new Node(null, 0, null);tail = new Node(null, 0, null);head.next = tail;tail.prev = head;}//根据索引位置找到结点private Node findNode(int index){int i = -1;//当p = tail时停止循环for(Node p = head; p != tail; p = p.next){if(i == index){return p;}}return null;}//在指定位置插入结点public void insert(int index , int value) throws IllegalArgumentException{Node prev = findNode(index - 1);if(prev == null){throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));}Node next = prev.next;Node newNode = new Node(prev, value, next);prev.next = newNode;next.prev = newNode;}//删除指定位置的结点public void remove(int index) throws IllegalArgumentException{Node prev = findNode(index - 1);if(prev == null){throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index - 1));}Node remove = prev.next;if(remove == tail){throw new IllegalArgumentException(String.format("Index %d 不合法%n ", index));}Node next = remove.next;//断开联系prev.next = next;next.prev = prev;}//在尾部结点前添加结点public void addLast(int index , int value) throws IllegalArgumentException{Node last = tail.prev;Node newNode = new Node(last, value, tail);last.next = newNode;tail.prev = newNode;}//删除最后一个结点public void removeLast() throws IllegalArgumentException{//没有结点的情况if(tail.prev == head){throw new IllegalArgumentException(String.format("Index %d 不合法%n ", 0));}Node remove = tail.prev;Node prev = remove.prev;prev.next = null;tail.prev = prev;}//迭代器@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = head.next;@Overridepublic boolean hasNext() {return p != tail;}@Overridepublic Integer next() {int value = p.value;p = p.next;return value;}};}}
四.双向循环链表的实现:
链表的最后一个节点指向第一个节点,形成一个闭环。
首先创造哨兵结点以及其构造函数:
private static class Node{Node prev;int value;Node next;public Node(Node prev, int value , Node next) {this.prev = prev;this.value = value;this.next = next;}}//哨兵节点private Node sentinel = new Node(null, -1, null);//哨兵节点构造函数public DoubleLinkedListCirtleSentinel(){sentinel.prev = sentinel;sentinel.next = sentinel;}
随后实现对双向循环链表的操作:
package LinkListStudy;import java.util.Iterator;public class DoubleLinkedListCirtleSentinel implements Iterable<Integer>{private static class Node{Node prev;int value;Node next;public Node(Node prev, int value , Node next) {this.prev = prev;this.value = value;this.next = next;}}//哨兵节点private Node sentinel = new Node(null, -1, null);//哨兵节点构造函数public DoubleLinkedListCirtleSentinel(){sentinel.prev = sentinel;sentinel.next = sentinel;}//添加节点到第一个 a <=> newNode <=> a(b)public void addFirst(int value){Node a = sentinel;//哨兵Node b = sentinel.next;Node newNode = new Node(a, value, b);a.next = newNode;b.prev = newNode;}//添加节点到最后一个public void addLast(int value){Node b = sentinel;Node a = sentinel.prev;Node newNode = new Node(a, value, b);a.next = newNode;b.prev = newNode;}//删除第一个public void removeFirst(){Node removed = sentinel.next;if(removed == sentinel){throw new IllegalArgumentException(String.format("Index %d 不合法%n ", 0));}Node a = sentinel;Node b = removed.next;a.next = b;b.prev = a;}//删除最后一个public void removeLast() throws IllegalArgumentException{Node removed = sentinel.prev;if(removed == sentinel){throw new IllegalArgumentException(String.format("Index %d 不合法%n ", 0));}Node a = removed.next;Node b = sentinel;a.next = b;b.prev = a;}//根据目标值删除public void removeByValue(int value){Node removed = findByValue(value);if(removed == null){return ;//不用删}Node a = removed.prev;Node b = removed.next;a.next = b;b.prev = a;}//寻找目标值索引位置public Node findByValue(int value){Node p = sentinel.next;while(p != sentinel){if(p.value == value){return p;}p = p.next;}return null;}//迭代器遍历@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = sentinel.next;@Overridepublic boolean hasNext() {return p != sentinel;}@Overridepublic Integer next() {int value = p.value;p = p.next;return value;}};}//递归函数private void recursion(Node curr){//某个节点要进行的操作if(curr == sentinel){return ;}System.out.println(curr.value);recursion(curr.next);}}
好了,看到这里感谢观看,记得三连支持,后序继续更新数据结构与算法相关知识!!!