双城网站建设公司,wordpress右侧,wordpress 上传目录权限设置密码,国家信用信息公示系统陕西目录 单向链表
初始
头插
思路
情况一 情况二
代码 尾插
思路
遍历
优化遍历
遍历验证头插
尾插代码
优化
尾插测试
get
思路
代码
测试
insert
思路
代码
优化
测试
remove
移除头结点
提问
移除指定位置
测试 单向链表
每个元素只知道自己的下一个…目录 单向链表
初始
头插
思路
情况一 情况二
代码 尾插
思路
遍历
优化遍历
遍历验证头插
尾插代码
优化
尾插测试
get
思路
代码
测试
insert
思路
代码
优化
测试
remove
移除头结点
提问
移除指定位置
测试 单向链表
每个元素只知道自己的下一个元素是谁最后一个元素的下一个元素为null 初始
public class SingleLinkedList {// 头指针private Node head;// 节点类 private对外隐藏细节DataAllArgsConstructorprivate static class Node {private int value;private Node next;}}
将内部类定义为静态主要有两个原因
实例化方式静态内部类的实例化不需要依赖于外部类。而普通的内部类在实例化时会隐含地包含一个对外部类的引用因此普通的非静态内部类不能脱离外部类实例而单独存在。访问方式静态内部类可以使用静态方法直接通过类名来访问外部类的静态成员而不需要创建外部类的实例。而普通的内部类需要先创建外部类的实例然后通过该实例来访问外部类的静态成员。 头插
思路
对于使用者来说我给你一个value值你要将我的这个value值放入到链表头结点处 情况一
一开始无节点现在新增一个新节点 head new Node(value, null); 情况二
一开始有节点现在新增一个新节点 head new Node(value, head);
新节点的next指针指向原来节点原来节点地址为头指针指向的地址 代码 public void addFirst(int value) {head new Node(value, head);}
为什么没有情况一
开始时head为null情况二包含情况一 尾插
思路
对于使用者来说我给你一个value值你要将我的这个value值放入到链表最后面
那我怎么知道你链表什么时候是最后面 遍历
遍历到最后一个节点此时它的next指针指向null 注意头指针是为了记录第一个节点地址不能动所以我定义一个可以移动的指针开始指向第一个节点 public void foreach() {Node p head;while (p ! null) {System.out.println(p.value);p p.next;}} 优化遍历
实际开发中你可能不是要打印而是对加进来的值有其他操作此时换成函数式编程 public void foreach(ConsumerInteger consumer) {Node p head;while (p ! null) {consumer.accept(p.value);p p.next;}} 遍历验证头插
public class Test {public static void main(String[] args) {SingleLinkedList singleLinkedList new SingleLinkedList();singleLinkedList.addFirst(8);singleLinkedList.addFirst(7);singleLinkedList.addFirst(6);singleLinkedList.addFirst(5);singleLinkedList.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 void addLast(int value) {if (head null) {addFirst(value);// 不要忘记return否则会有相同值return;}Node p head;while (p.next ! null) {p p.next;}p.next new Node(value, null);} 尾插测试
public class Test {public static void main(String[] args) {SingleLinkedList singleLinkedList new SingleLinkedList();singleLinkedList.addLast(8);singleLinkedList.addLast(7);singleLinkedList.addLast(6);singleLinkedList.addLast(5);singleLinkedList.foreach(System.out::println);}
} get
思路
list(index) 是通过给一个索引然后得到该索引对应位置的值。
对于链表给一个索引返回该节点的值。 代码 public int get(int index) {int i 0;Node p head;while (p ! null) {if (i index) {return p.value;} else {p p.next;i;}}throw new IllegalArgumentException(索引越界异常);} 也可以用for循环写
public Node findNode(int index) {int i 0;for (Node p head; p ! null; p p.next, i) {if (i index) {return p;}}return null;
}public int get(int index) {Node node findNode(index);if (node null) {throw new IllegalArgumentException(StringUtils.format(索引: {} 不合法, index));}return node.value;
} 测试
public class Test {public static void main(String[] args) {SingleLinkedList singleLinkedList new SingleLinkedList();singleLinkedList.addLast(8);singleLinkedList.addLast(7);singleLinkedList.addLast(6);singleLinkedList.addLast(5);singleLinkedList.foreach(System.out::println);System.out.println();System.out.println(singleLinkedList.get(0));}
} insert
思路
我要向某个位置插入某个值那么我需要知道这个位置的前面一个节点(其next 指向当前位置)代码 public void insert(int index, int value) {Node 前节点 findNode(index - 1);if (前节点 null) throw new IllegalArgumentException(索引越界异常);前节点.next new Node(value, 前节点.next);} private Node findNode(int index) {int i 0;Node p head;while (p ! null) {if (i index) {return p;} else {p p.next;i;}}return null;}
index 0时此时返回null抛出异常显然不对 优化
index0时插入即头插 public void insert(int index, int value) {if (index 0) {addFirst(value);return;}Node 前节点 findNode(index - 1);if (前节点 null) throw new IllegalArgumentException(索引越界异常);前节点.next new Node(value, 前节点.next);} 测试
public class Test {public static void main(String[] args) {SingleLinkedList singleLinkedList new SingleLinkedList();singleLinkedList.addLast(8);singleLinkedList.addLast(7);singleLinkedList.addLast(6);singleLinkedList.addLast(5);singleLinkedList.foreach(System.out::println);System.out.println();singleLinkedList.insert(2, 100);singleLinkedList.foreach(System.out::println);}
} remove
移除头结点 public void removeFirst() {if (head null) {return;}head head.next;} 提问
1这个节点还存在有没有因此而造成内存泄露
不会1节点无引用指向他JVM垃圾回收会处理 移除指定位置 public void remove(int index) {if (index 0) {removeFirst();return;}Node 前节点 findNode(index - 1);if (前节点 null) throw new IllegalArgumentException(索引越界异常);前节点.next 前节点.next.next;} 测试
public class Test {public static void main(String[] args) {SingleLinkedList singleLinkedList new SingleLinkedList();singleLinkedList.addLast(8);singleLinkedList.addLast(7);singleLinkedList.addLast(6);singleLinkedList.addLast(5);singleLinkedList.foreach(System.out::println);System.out.println();singleLinkedList.insert(2, 100);singleLinkedList.foreach(System.out::println);System.out.println();singleLinkedList.remove(4);singleLinkedList.foreach(System.out::println);}
}
