当前位置： 首页 > news >正文

网站建设网络推广加盟东莞seo优化

news 2025/8/3 0:08:56
网站建设网络推广加盟,东莞seo优化,网络seo培训,博客和微博的区别目录 链表 单向链表 哨兵链表 双向链表 环形链表 链表 链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。 随机访问性能 根据 index 查找，时间复杂度 O(n) 插入或删除性能 起始位置：O(1)结束位…

目录

链表

单向链表

哨兵链表

双向链表

环形链表

链表

链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。

随机访问性能

根据 index 查找，时间复杂度 O(n)

插入或删除性能

  • 起始位置：O(1)
  • 结束位置：如果已知 tail 尾节点是 O(1)[双向链表]，不知道 tail 尾节点是 O(n)
  • 中间位置：根据 index 查找时间 + O(1)

单向链表

单向链表中每个元素只知道下一个节点位置

单向链表的简单实现

public class SinglyLinkList implements Iterable<Integer> {private Node head = null;//节点类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, head);}//向链表尾部添加节点public void addLast(int value) {Node last = findLast();if (last == null) {addFirst(value);}last.next = new Node(value, null);}private Node findLast() {if (head.next == null) {return null;}Node p = head;while (p.next != null) {p = p.next;}return p;}//遍历链表public void loop(Consumer<Integer> consumer) {Node pointer = head;while (pointer != null) {consumer.accept(pointer.value);pointer = pointer.next;}}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node pointer = head;@Overridepublic boolean hasNext() {return pointer != null;}@Overridepublic Integer next() {int value = pointer.value;pointer = pointer.next;return value;}};}// 根据索引查找节点值private Node findByIndex(int index) {int i = 0;for (Node p = head; p != null; p = p.next, i++) {if (index == i) {return p;}}return null;}public int get(int index) {Node node = findByIndex(index);if (node == null) {throw new IllegalArgumentException("索引超出范围");}return node.value;}//插入元素public void insert(int index, int value) {if (index == 0) {addFirst(value);return;}//查找索引的上一个节点Node node = findByIndex(index - 1);if (node == null) {throw new IllegalArgumentException("索引超出范围");}node.next = new Node(value, node.next);}//移除首节点public void removeFirst() {if (head==null){throw new RuntimeException("链表为空。无法移除");}head = head.next;}//删除指定节点public void remove(int index){if (index==0){removeFirst();}//找到要删除的节点的前驱节点Node node = findByIndex(index - 1);Node remove = node.next;if (remove==null){//要删除的节点位置为空throw new IllegalArgumentException("索引越界");}node.next = remove.next;}
}

这种实现方法有一个弊端，那就是每次添加或是删除元素时都需要进行判断链表是否为空。因此提出了哨兵链表的概念

哨兵链表

所谓哨兵列表，就是头节点不存储数据，只为简化边缘判断使用。

具体代码如下

public class SinglyLinkListSentinel implements Iterable<Integer> {//头节点指向哨兵节点。值可以随便给private Node head = new Node(723468, null);//节点类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) {//在链表头部添加节点时，应该在哨兵之后。insert(0, value);}//向链表尾部添加节点public void addLast(int value) {Node last = findLast();last.next = new Node(value, null);}private Node findLast() {Node p = head;while (p.next != null) {p = p.next;}return p;}//遍历链表public void loop(Consumer<Integer> consumer) {//从哨兵节点之后的节点开始遍历Node pointer = head.next;while (pointer != null) {consumer.accept(pointer.value);pointer = pointer.next;}}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node pointer = head.next;@Overridepublic boolean hasNext() {return pointer != null;}@Overridepublic Integer next() {int value = pointer.value;pointer = pointer.next;return value;}};}// 根据索引查找节点值private Node findByIndex(int index) {//这里设置为-1是排除哨兵节点带来的影响int i = -1;for (Node p = head; p != null; p = p.next, i++) {if (index == i) {return p;}}return null;}public int get(int index) {Node node = findByIndex(index);if (node == null) {throw new IllegalArgumentException("索引超出范围");}return node.value;}//插入元素public void insert(int index, int value) {//查找索引的上一个节点Node node = findByIndex(index - 1);if (node == null) {throw new IllegalArgumentException("索引超出范围");}node.next = new Node(value, node.next);}//移除首节点public void removeFirst() {remove(0);}//删除指定节点public void remove(int index) {//找到要删除的节点的前驱节点Node node = findByIndex(index - 1);Node remove = node.next;if (remove == null) {//要删除的节点位置为空throw new IllegalArgumentException("索引越界");}node.next = remove.next;}
}

双向链表

每个元素知道上一个元素与下一个元素的地址

简单实现如下

public class DoublyLinkedListSentinel implements Iterable<Integer>{//头哨兵private Node head = new Node(null, null, 0);//尾哨兵private Node tail = new Node(null, null, 0);public DoublyLinkedListSentinel() {//初始化时，对头尾哨兵进行指定head.next = tail;tail.prev = head;}private static class Node {Node prev;Node next;int value;public Node(Node prev, Node next, int value) {this.prev = prev;this.next = next;this.value = value;}}//提供双向链表方法public Node findByIndex(int index) {int i = -1;for (Node p = head; p != tail; p = p.next, i++) {if (index == i) {return p;}}return null;}//插入首元素public void addFirst(int value) {insert(0, value);}//插入元素public void insert(int index, int value) {Node prev = findByIndex(index - 1);if (prev == null) {throw new RuntimeException("下标越界");}Node next = prev.next;Node node = new Node(prev, next, value);prev.next = node;next.prev = node;}//向尾节点添加public void addLast(int value){Node prev = tail.prev;Node addNode = new Node(prev, tail, value);prev.next = addNode;tail.prev = addNode;}//删除首节点public void removeFirst(){if (head.next==tail){throw new RuntimeException("链表为空");}Node remove = head.next;Node next = remove.next;head.next = next;next.prev = head;}//删除元素public void remove(int index) {Node prev = findByIndex(index - 1);if (prev == null) {throw new RuntimeException("下标越界");}Node remove = prev.next;Node next = remove.next;if (remove==tail){throw new RuntimeException("下标越界");}prev.next = next;next.prev = prev;}//获取元素public int get(int index){Node node = findByIndex(index);return node.value;}//遍历元素public void loop(Consumer<Integer> consumer) {Node pointer = head.next;while (pointer != tail) {consumer.accept(pointer.value);pointer = pointer.next;}}//迭代器实现@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;}};}
}

环形链表

环形链表的尾节点指向的是头节点head

环形链表我们也可以引入哨兵，空链表时，哨兵既做头节点也做尾节点。

简单实现代码如下

public class DoublyLinkedListSentinelTo implements Iterable<Integer> {private Node sentinel = new Node(null, null, -1);public DoublyLinkedListSentinelTo() {sentinel.prev = sentinel;sentinel.next = sentinel;}@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 static class Node {Node prev;Node next;int value;public Node(Node prev, Node next, int value) {this.prev = prev;this.next = next;this.value = value;}}//提供循环链表的方法public Node findByIndex(int index) {int i = 0;for (Node p = sentinel.next; p != sentinel; i++, p = p.next) {if (index == i) {return p;}}return null;}public void addFirst(int value) {Node next = sentinel.next;Node addNode = new Node(sentinel, next, value);sentinel.next = addNode;next.prev = addNode;}public void insert(int index, int value) {if (index == 0) {addFirst(value);}Node prev = findByIndex(index - 1);if (prev == null) {throw new RuntimeException("下标越界");}Node next = prev.next;Node insertNode = new Node(prev, next, value);next.prev = insertNode;prev.next = insertNode;}public void addLast(int value) {Node prev = sentinel.prev;Node addNode = new Node(prev, sentinel, value);prev.next = addNode;sentinel.prev = addNode;}//删除第一个节点public void removeFirst() {Node remove = sentinel.next;if (remove == sentinel) {throw new RuntimeException("下标越界");}Node next = remove.next;sentinel.next = next;next.prev = sentinel;}//删除最后一个节点public void removeLast() {Node remove = sentinel.prev;if (remove == sentinel) {throw new RuntimeException("下标越界");}Node prev = remove.prev;prev.next = sentinel;sentinel.prev = prev;}//删除指定删除节点public void remove(int index) {if (index == 0) {removeFirst();}Node prev = findByIndex(index - 1);Node remove = prev.next;if (remove == sentinel) {throw new RuntimeException("下标越界");}Node next = remove.next;prev.next = next;next.prev = prev;}//遍历节点public void loop(Consumer<Integer> consumer) {for (Node p = sentinel.next; p != sentinel; p = p.next) {consumer.accept(p.value);}}
}

http://www.mmbaike.com/news/76087.html

相关文章：

  • 单位网站平台建设汇报南昌百度快速排名提升
  • 乌鲁木齐做网站哪家好拉新推广渠道
  • 如何向搜索引擎提交网站典型的网络营销案例
  • 网站建设周期计划b站推广网站2022
  • 有没有做那个的视频网站吗河南做网站的
  • 大流量网站解决访问量网站域名服务器查询
  • 郑州哪家公司给国外做网站热搜榜百度一下你就知道
  • 天津网站开发建设搜索引擎营销策略有哪些
  • 临沂企业建站模板真正免费的建站
  • ios网站开发视频教程湖口网站建设
  • 建湖做网站找哪家好seo外包优化网站
  • 网站搭建前景手机百度
  • wordpress修改固定连接插件汕尾网站seo
  • 邯郸手机网站建设报价镇江百度推广公司
  • 网站调用视频外包公司的优势和劣势
  • 组织建设 湖南省直工会网站原创软文
  • 路桥做网站完整的社群营销方案
  • 网站开发的具体流程搜索引擎优化的内容有哪些
  • 河北网站建站制作轻饮食网络推广方案
  • 网站建设图标整合营销推广
  • 建设网站 报告书郴州网站建设网络推广平台
  • 做门名片设计网站企业网络营销目标
  • 专业做网站建设360搜索指数
  • 天津网站优化流程宁波关键词优化平台
  • 旅游网站优化方案谷歌seo搜索
  • 买2g 空间做下载网站黑帽seo技巧
  • 有没有做课题很好的网站独立网站
  • 网站模板视频教程广州百度网站快速排名
  • 龙华网站建设方案案例硬件优化大师下载
  • 安卓app做网站外壳新郑网络推广外包