当前位置: 首页> 汽车> 时评 > 建设行业_广告设计公司实习日记_互联网推广营销_自助建站平台

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

时间:2025/7/10 16:48:26来源:https://blog.csdn.net/2302_79840586/article/details/142654998 浏览次数: 0次
建设行业_广告设计公司实习日记_互联网推广营销_自助建站平台

目录

一.什么是链表?

链表的类型

链表的特点

使用场景:

二.单向链表的实现:

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

然后创造头结点(哨兵结点),方便找到固定的位置来对链表进行操作:

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

三.双向链表的实现:

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

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

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

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

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

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

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


一.什么是链表?

链表(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);}}

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

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: