做美食的网站可以放些小图片,做pc网站排,企业邮箱注册价格,网站制作建目录
单向链表哨兵
初始
头插
思路
代码
尾插
思路
遍历
遍历验证头插
尾插代码
尾插测试
get
思路
代码
测试
insert
思路
代码
测试
remove
移除头结点
提问
移除指定位置
测试 单向链表哨兵
单向链表里面有一个特殊的节点称为哨兵节点#xff0c;…目录
单向链表哨兵
初始
头插
思路
代码
尾插
思路
遍历
遍历验证头插
尾插代码
尾插测试
get
思路
代码
测试
insert
思路
代码
测试
remove
移除头结点
提问
移除指定位置
测试 单向链表哨兵
单向链表里面有一个特殊的节点称为哨兵节点不存储数据。
优势简化了单向链表的空判断例如 尾插、get、insert、remove 初始 public class SentinelLinkedListTest {// 头指针 指向哨兵(666是任意定义的一个值)private Node head new Node(666, null);// 节点类 private对外隐藏细节DataAllArgsConstructorprivate static class Node {private int value;private Node next;}} 将内部类定义为静态主要有两个原因
实例化方式静态内部类的实例化不需要依赖于外部类。而普通的内部类在实例化时会隐含地包含一个对外部类的引用因此普通的非静态内部类不能脱离外部类实例而单独存在。 访问方式静态内部类可以使用静态方法直接通过类名来访问外部类的静态成员而不需要创建外部类的实例。而普通的内部类需要先创建外部类的实例然后通过该实例来访问外部类的静态成员。 头插
思路
对于使用者来说我给你一个value值你要将我的这个value值放入到链表头结点处。
不同于单向链表这里一开始就有了哨兵
代码 public void addFirst(int value) {head.next new Node(value, head.next);} 哨兵的next指针指向新节点新节点的next指针为之前哨兵的next指针指向的节点 尾插
思路
对于使用者来说我给你一个value值你要将我的这个value值放入到链表最后面
那我怎么知道你链表什么时候是最后面 遍历
遍历到最后一个节点此时它的next指针指向null 注意头指针是为了记录第一个节点地址不能动所以我定义一个可以移动的指针开始指向第一个节点 public void foreach(ConsumerInteger consumer) {Node p head.next;while (p ! null) {consumer.accept(p.value);p p.next;}} 注不同于单向链表自定义的指针开始是指向哨兵的下一个节点地址。 遍历验证头插 public class SentinelTest {public static void main(String[] args) {SentinelLinkedListTest sentinelLinkedListTest new SentinelLinkedListTest();sentinelLinkedListTest.addFirst(8);sentinelLinkedListTest.addFirst(7);sentinelLinkedListTest.addFirst(6);sentinelLinkedListTest.addFirst(5);sentinelLinkedListTest.foreach(System.out::println);}
}
为什么是倒序
头插先插的会随着后续插入一次次向后挪动 尾插代码
通过遍历可以知道指针指向过最后一个节点后然后指向了null
那让指针一直指最后一次的下一个节点不为null时为我们所需要的节点 public void addLast(int value) {Node p head;while (p.next ! null) {p p.next;}p.next new Node(value, null);} 注意不带哨兵的单向链表如果链表啥也没有那么p.next直接空指针
而现在头指针指向哨兵就不可能存在空指针这种情况 尾插测试 public class SentinelTest {public static void main(String[] args) {SentinelLinkedListTest sentinelLinkedListTest new SentinelLinkedListTest();sentinelLinkedListTest.addLast(99);sentinelLinkedListTest.foreach(System.out::println);}
} get
思路
list(index) 是通过给一个索引然后得到该索引对应位置的值。
对于链表给一个索引返回该节点的值。 代码 public int get(int index) {Node node findNode(index);if (node null) throw new IllegalArgumentException(索引越界);return node.value;}public Node findNode(int index) {int i -1;Node p head;while (p ! null) {if (i index) {return p;} else {p p.next;i;}}return null;} 注不同于单向链表这里开始就让 i 为 -1 代表哨兵的位置 p 指向head也就是哨兵 测试
public class SentinelTest {public static void main(String[] args) {SentinelLinkedListTest sentinelLinkedListTest new SentinelLinkedListTest();sentinelLinkedListTest.addFirst(8);sentinelLinkedListTest.addFirst(7);sentinelLinkedListTest.addFirst(6);sentinelLinkedListTest.addFirst(5);sentinelLinkedListTest.addLast(99);sentinelLinkedListTest.foreach(System.out::println);System.out.println();System.out.println(sentinelLinkedListTest.get(4));}
} insert
思路
我要向某个位置插入某个值那么我需要知道这个位置的前面一个节点(其next 指向当前位置)代码 public void insert(int index, int value) {Node 前节点 findNode(index - 1);if (前节点 null) throw new IllegalArgumentException(索引越界);前节点.next new Node(value, 前节点.next);}
此处现在也不同判断index为0时的插入-1位置代表的就是哨兵 测试
public class SentinelTest {public static void main(String[] args) {SentinelLinkedListTest sentinelLinkedListTest new SentinelLinkedListTest();sentinelLinkedListTest.addFirst(8);sentinelLinkedListTest.addFirst(7);sentinelLinkedListTest.addFirst(6);sentinelLinkedListTest.addFirst(5);sentinelLinkedListTest.addLast(99);sentinelLinkedListTest.foreach(System.out::println);System.out.println();System.out.println(sentinelLinkedListTest.get(4));System.out.println();sentinelLinkedListTest.insert(0, 100);sentinelLinkedListTest.foreach(System.out::println);}
} remove
移除头结点 public void removeFirst() {if (head.next null) {return;}head.next head.next.next;} 提问
移除的节点还存在有没有因此而造成内存泄露
不会移除的节点无引用指向他JVM垃圾回收会处理 移除指定位置 public void remove(int index) {Node 前节点 findNode(index - 1);if (前节点 null) throw new IllegalArgumentException(索引越界);前节点.next 前节点.next.next;} 测试
public class SentinelTest {public static void main(String[] args) {SentinelLinkedListTest sentinelLinkedListTest new SentinelLinkedListTest();sentinelLinkedListTest.addFirst(8);sentinelLinkedListTest.addLast(99);sentinelLinkedListTest.foreach(System.out::println);System.out.println();sentinelLinkedListTest.insert(0, 100);sentinelLinkedListTest.foreach(System.out::println);System.out.println();sentinelLinkedListTest.removeFirst();sentinelLinkedListTest.foreach(System.out::println);System.out.println();sentinelLinkedListTest.remove(0);sentinelLinkedListTest.foreach(System.out::println);}
}
