建设行业_广告设计公司实习日记_互联网推广营销_自助建站平台

目录

一.什么是链表？

链表的类型

链表的特点

使用场景：

二.单向链表的实现：

首先创建节点类以及对应的构造方法：

然后创造头结点（哨兵结点），方便找到固定的位置来对链表进行操作：

最后列出简单的对链表的增删改查操作： 

三.双向链表的实现：

首先创建节点类以及对应的构造方法：

 然后创建头尾哨兵，便于在两哨兵中间插入元素以及双向链表的操作：

随后创建这个双向链表的构造方法：

最后实现对双向链表的操作： 

四.双向循环链表的实现：

 首先创造哨兵结点以及其构造函数：

随后实现对双向循环链表的操作： 

---

一.什么是链表？

链表（Linked List） 是一种线性数据结构，其中元素称为节点（Node）。每个节点包含两个部分：

1. 数据域（data）：存储节点的值。
2. 指针域（next）：存储下一个节点的地址（或引用），指向链表中的下一个节点。

与数组不同，链表的元素在内存中不一定连续存储。链表的灵活性在于可以动态调整大小，因为元素的插入和删除操作不涉及移动其他元素。

链表的类型

1. 单向链表（Singly Linked List）：每个节点只有一个指针指向下一个节点。
2. 双向链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。
3. 循环链表（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);}}

---

好了，看到这里感谢观看，记得三连支持，后序继续更新数据结构与算法相关知识！！！