网站制作案例市场,中国网站备案,html5基础知识,全国首批9所重点马院网站建设五种List集合的简单实现 一、数组形式二、单向链表形式三、含哨兵节点的单向链表形式四、含哨兵节点的双向链表形式五、含哨兵节点的环形链表形式 本文是对不同形式List集合的增删改查实现#xff0c;仅是对学习过程进行记录 一、数组形式
关键点#xff1a;
有三个成员变量… 五种List集合的简单实现 一、数组形式二、单向链表形式三、含哨兵节点的单向链表形式四、含哨兵节点的双向链表形式五、含哨兵节点的环形链表形式 本文是对不同形式List集合的增删改查实现仅是对学习过程进行记录 一、数组形式
关键点
有三个成员变量集合对象array、元素个数size、数组长度capacity在扩容时将旧array中的数据拷贝到新array对象中新增先处理add(int index, int data)方法考虑扩容、后移元素、赋值三个步骤
public class SelfArrayList {/*** 真实的数据*/private int[] array {};/*** 集合真实大小*/private int size 0;/*** 集合容量*/private int capacity 8;public void add(int data) {initAndGroup();add(size, data);}public void add(int index, int data) {initAndGroup();// 仅支持将元素添加到当前集合最后位置if (index size) {for (int i size; i index; i--) {array[i] array[i - 1];}array[index] data;size;}}public int delete() {return array[--size];}public void update(int index, int data) {if (index 0 index size) {array[index] data;}}public int get(int index) {return array[index];}public void forEach(ConsumerInteger consumer) {for (int i 0; i size; i) {consumer.accept(array[i]);}}private void initAndGroup() {if (size 0) {array new int[capacity];} else if (size capacity) {capacity capacity 1;int[] newArray new int[capacity];System.arraycopy(array, 0, newArray, 0, size);array newArray;}}
}二、单向链表形式
关键点
成员变量就一个Node head节点主要是三个关键方法add(int index, int value)、delete(int index)、findNode(int index)三个方法里面findNode(int index)又是关键
public class SelfLinkList {private Node head null;public void addHead(int value) {head new Node(value, head);}public void addTail(int value) {Node tail findTail();// 加入的节点为第一个节点if (tail null) {addHead(value);} else {tail.next new Node(value, null);}}/*** 核心方法 1 of 3*/public void add(int index, int value) {if (index 0) {addHead(value);return;}// 找到对应索引的上一个节点Node pre findNode(index - 1);if (pre null) {return;}pre.next new Node(value, pre.next);}public Node deleteFirst() {Node deleteNode head;head head.next;return deleteNode;}/*** 核心方法 2 of 3*/public Node delete(int index) {Node pre findNode(index - 1);// 删除头节点数据if (pre null) {return deleteFirst();}Node cur pre.next;// 删除末尾不存在数据if (cur null) {return null;}pre.next cur.next;return cur;}/*** 核心方法 3 of 3* index 小于0或者大于链表长度 返回null*/public Node findNode(int index) {Node temp head;int nodeSize 0;// 循环遍历 找到对应的节点while (temp ! null) {if (index nodeSize) {return temp;}temp temp.next;nodeSize;}return null;}public void forEach(ConsumerInteger consumer) {Node temp head;while (temp ! null) {consumer.accept(temp.value);temp temp.next;}}private Node findTail() {if (head null) {return head;}Node tail head;while (tail.next ! null) {tail tail.next;}return tail;}AllArgsConstructorpublic static class Node {public int value;public Node next;}
}三、含哨兵节点的单向链表形式
关键点
自带一个head节点其目的是为了简化后续的操作流程避免出现null的场景主要是三个关键方法add(int index, int value)、delete(int index)、findNode(int index)三个方法里面findNode(int index)又是关键特别注意哨兵节点和普通参数节点返回下标的差异
public class SelfSentinelLinkList {private final SelfSentinelLinkList.Node head new SelfSentinelLinkList.Node(0, null);public void addHead(int value) {add(0, value);}public void addTail(int value) {SelfSentinelLinkList.Node tail findTail();tail.next new SelfSentinelLinkList.Node(value, null);}/*** 核心方法 1 of 3*/public void add(int index, int value) {SelfSentinelLinkList.Node pre findNode(index - 1);// 添加元素超过链表长度if (pre null) {return;}pre.next new SelfSentinelLinkList.Node(value, pre.next);}public SelfSentinelLinkList.Node deleteFirst() {return delete(0);}/*** 核心方法 2 of 3*/public SelfSentinelLinkList.Node delete(int index) {SelfSentinelLinkList.Node pre findNode(Math.max(-1, index - 1));// 删除索引下标超过链表长度if (pre null) {return null;}SelfSentinelLinkList.Node deleted pre.next;// 删除索引下标超过链表长度if (deleted null) {return null;}pre.next deleted.next;return deleted;}/*** 核心方法 3 of 3* 哨兵节点 index-1* 数据节点 index0*/public SelfSentinelLinkList.Node findNode(int index) {SelfSentinelLinkList.Node temp head;int nodeSize -1;while (temp ! null) {if (index nodeSize) {return temp;}temp temp.next;nodeSize;}return null;}public void forEach(ConsumerInteger consumer) {SelfSentinelLinkList.Node temp head.next;while (temp ! null) {consumer.accept(temp.value);temp temp.next;}}private SelfSentinelLinkList.Node findTail() {SelfSentinelLinkList.Node tail head;while (tail.next ! null) {tail tail.next;}return tail;}AllArgsConstructorpublic static class Node {public int value;public SelfSentinelLinkList.Node next;}
}四、含哨兵节点的双向链表形式
关键点
默认初始化两个节点head、tail每增加一个数据就new一个Node并且同时维护前后4条关系链new Node的时候已经维护了两条删除同理主要是三个关键方法add(int index, int value)、delete(int index)、findNode(int index)三个方法里面findNode(int index)又是关键
public class SelfSentinelDoublyLinkedList {/*** 头哨兵*/private final Node head new Node(null, 0, null);/*** 尾哨兵*/private final Node tail new Node(null, 0, null);public SelfSentinelDoublyLinkedList() {head.next tail;tail.prev head;}public void addFirst(int value) {add(0, value);}/*** 双向链表的特色地方 就是在操作last的时候*/public void addLast(int value) {Node last tail.prev;Node added new Node(last, value, tail);last.next added;tail.prev added;}/*** 新增数据 核心方法 1 of 3*/public void add(int index, int value) {// 找到要插入数据的上一个节点Node prev findNode(index - 1);if (prev null) {return;}Node next prev.next;Node inserted new Node(prev, value, next);prev.next inserted;next.prev inserted;}public void deleteFirst() {delete(0);}public void deleteLast() {Node removed tail.prev;if (removed head) {return;}Node prev removed.prev;prev.next tail;tail.prev prev;}/*** 删除数据 核心方法 2 of 3*/public void delete(int index) {Node prev findNode(index - 1);if (prev null) {return;}Node removed prev.next;if (removed tail) {return;}Node next removed.next;prev.next next;next.prev prev;}/*** 根据索引查找数据 核心方法 3 of 3*/private Node findNode(int index) {int i -1;for (Node p head; p ! tail; p p.next, i) {if (i index) {return p;}}return null;}public void forEach(ConsumerInteger consumer) {Node p head.next;while (p ! tail) {consumer.accept(p.value);p p.next;}}static class Node {/*** 上一个节点指针*/private Node prev;/*** 下一个节点指针*/private Node next;/*** 具体数据*/private final int value;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}
}五、含哨兵节点的环形链表形式
关键点
默认只初始化一个节点sentinel由于是一个环所以该节点既可以是头哨兵也可以是尾哨兵。增加一个数据就new一个Node并且同时维护前后4条关系链new Node的时候已经维护了两条在初始化SelfRingLinkedListSentinel这个链表的时候构建好环的关联关系新增、删除数据时都需要维护好四条关系链
public class SelfRingLinkedListSentinel {/*** 哨兵节点*/private final Node sentinel new Node(null, 0, null);public SelfRingLinkedListSentinel() {sentinel.next sentinel;sentinel.prev sentinel;}/*** 添加到第一个*/public void addFirst(int value) {Node next sentinel.next;Node prev sentinel;Node added new Node(prev, value, next);prev.next added;next.prev added;}/*** 添加到最后一个*/public void addLast(int value) {Node prev sentinel.prev;Node next sentinel;Node added new Node(prev, value, next);prev.next added;next.prev added;}/*** 删除第一个*/public void removeFirst() {Node removed sentinel.next;if (removed sentinel) {return;}Node a sentinel;Node b removed.next;a.next b;b.prev a;}/*** 删除最后一个*/public void removeLast() {Node removed sentinel.prev;if (removed sentinel) {return;}Node a removed.prev;Node b sentinel;a.next b;b.prev a;}/*** 根据值删除节点*/public void removeByValue(int value) {Node removed findNodeByValue(value);if (removed ! null) {Node prev removed.prev;Node next removed.next;prev.next next;next.prev prev;}}/*** 遍历找到对应的元素*/private Node findNodeByValue(int value) {Node p sentinel.next;while (p ! sentinel) {if (p.value value) {return p;}p p.next;}return null;}public void forEach(ConsumerInteger consumer) {Node p sentinel.next;while (p ! sentinel) {consumer.accept(p.value);p p.next;}}static class Node {int value;Node prev;Node next;public Node(Node prev, int value, Node next) {this.prev prev;this.value value;this.next next;}}
}
