达州做网站,企业安全文化建设做法,企业做网站的方案,如何申请做网站目录 1. 双向不带头非循环链表的介绍2. 相关功能的实现2.1 基本框架2.2 size2.3 addFirst2.4 addLast2.5 addIndex2.6 contains2.7 remove2.8 removeAllKey2.9 clear 3. 全部代码 前面我们学习了最简单的链表#xff1a;单链表#xff0c;今天我们学习双向不带头非循环链表单链表今天我们学习双向不带头非循环链表这也是Java的集合框架中LinkedList的底层实现
1. 双向不带头非循环链表的介绍
双向指的是每个链表结点有三个域一个是数据域另外两个保存了前驱结点的地址和后继结点的地址如图第一个结点的前驱为null最后一个结点的后继也为null
2. 相关功能的实现
2.1 基本框架
同样定义泛型类myLinkedList每个结点定义为静态内部类ListNode提供构造方法给val初始化定义结点first表示链表的第一个结点定义last表示链表的最后一个结点
public class myLinkedListT {//结点类static class ListNode {public ListNode prev;//前驱public Object val;//数据public ListNode next;//后继//构造方法public ListNode(Object val) {this.val val;}}public ListNode first;//第一个结点public ListNode last;//最后一个结点//....其他方法
}2.2 size
size的功能是获取链表长度定义计数器size遍历链表每个结点每遍历一个结点size1直至遍历完链表返回size //得到单链表的长度public int size() {int size 0;ListNode cur first;while (cur ! null) {cur cur.next;size;}return size;}
2.3 addFirst
addFirst意为头插在链表的头部插入数据如果链表没有数据first等于null则让first和last等于新的结点然后return如果链表已有数据先让新的结点绑定链表再让原来的头部的prev指向新的结点接着更新first //头插法public void addFirst(T val) {ListNode newNode new ListNode(val);//如果没有元素if (first null) {first last newNode;return;}newNode.next first;first.prev newNode;first newNode;}2.4 addLast
addLast表示尾插在链表尾部插入数据如果链表没有数据让first和last等于新的结点然后return如果链表已有数据让新的结点的prev指向链表的last接着让last的next指向新的结点然后更新last的值 //尾插法public void addLast(T val) {ListNode newNode new ListNode(val);//如果没有元素if (last null) {first last newNode;return;}newNode.prev last;last.next newNode;last newNode;}2.5 addIndex
addIndex表示在Index位置插入数据插入前需要判断Index的合法性Index不能小于0不能大于链表的长度定义IndexNotLegalException异常类如果Index不合法就抛出这个异常
public class IndexNotLegalException extends RuntimeException {public IndexNotLegalException(String s) {super(s);}public IndexNotLegalException() {super();}
}如果Index等于0表示头插如果Index等于链表长度表示尾插此时直接调用方法在插入之前先找到Index位置的结点接着先绑定后面的数据 //任意位置插入,第一个数据节点为0号下标public void addIndex(int index, T val) {ListNode newNode new ListNode(val);//index合法性检查try {if (index 0 || index size()) {throw new IndexNotLegalException(Index不合法);}} catch (IndexNotLegalException e) {e.printStackTrace();}//index0 头插if (index 0) {addFirst(val);return;}//indexsize 尾插if (index size()) {addLast(val);return;}//ListNode cur first;for (int i 0; i index; i) {cur cur.next;}ListNode prev cur.prev;//开始绑定newNode.next cur;newNode.prev prev; prev.next newNode;cur.prev newNode;}2.6 contains
查找链表中是否包含某个数据key如果包含返回true否则返回false //查找是否包含关键字key是否在单链表当中public boolean contains(T key) {if (first null) {return false;}ListNode cur first;while (cur ! null) {if (cur.val.equals(key)) {return true;}cur cur.next;}return false;}2.7 remove
删除链表中第一个值为key的结点如果链表为空直接返回。定义del来遍历链表如果del的值与key相等分情况讨论 1.del为第一个结点此时只需将first指向下一个结点即可 2.del为最后一个结点此时将last指向前一个结点然后将last的next置为空 3.一般情况要删除的结点在中间定义两个变量prevNode表示要删除的结点的前一个结点nextNode表示要删除的结点的后一个结点让prevNode的next指向nextNode让nextNode的prev指向prevNode此时就跳过了要删除的结点没人引用它也就意味着删除了它 //删除第一次出现关键字为key的结点public void remove(T key) {if (first null) {return;}ListNode del first;while (del ! null) {if (del.val.equals(key)) {//删除ListNode preNode del.prev;ListNode nextNode del.next;//prenull?if (pre null) {//第一个是keyfirst first.next;return;}if (next null) {//最后一个是keylast last.prev;last.next null;return;}preNode.next nextNode;nextNode.prev preNode;return;}del del.next;}}2.8 removeAllKey
删除链表中所有值为key的结点分情况讨论 1.前面部分全是要删除的结点first往后走如果first为空了说明整个链表的值都是key这个时候直接return 2.后面部分全是要删除的结点让last往前走 3.一般情况情况1处理了链表前部分都是key的情况情况2处理了链表后部分都是key的情况此时的key只能出现在中间部分删除的逻辑remove一样只不过remove删除完一个之后return了removeAllKey则是删除之后继续删除 //删除所有值为key的结点public void removeAllKey(T key) {if (first null) {return;}//处理前面的keywhile (first.val.equals(key)) {first first.next;if (first null) {return;}}//处理后面的keywhile (last.val.equals(key)) {last last.prev;last.next null;}//ListNode del first;while (del ! null) {if (del.val.equals(key)) {//删除ListNode preNode del.prev;ListNode nextNode del.next;//preNode.next next;nextNode.prev preNode;}del del.next;}}2.9 clear
clear表示将链表置空只需循环遍历链表将每一个结点都置空 public void clear() {while (first ! null) {ListNode next first.next;first.prev first.next null;first next;}last null;}3. 全部代码
//不带头 双向 非循环 链表
public class myLinkedListT {//结点类static class ListNode {public ListNode prev;//前驱public Object val;//数据public ListNode next;//后继//构造方法public ListNode(Object val) {this.val val;}}public ListNode first;//第一个结点public ListNode last;//最后一个结点//头插法public void addFirst(T val) {ListNode newNode new ListNode(val);//如果没有元素if (first null) {first last newNode;return;}newNode.next first;first.prev newNode;first newNode;}//尾插法public void addLast(T val) {ListNode newNode new ListNode(val);//如果没有元素if (last null) {first last newNode;return;}newNode.prev last;last.next newNode;last newNode;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index, T val) {ListNode newNode new ListNode(val);//index合法性检查try {if (index 0 || index size()) {throw new IndexNotLegalException(Index不合法);}} catch (IndexNotLegalException e) {e.printStackTrace();}//index0 头插if (index 0) {addFirst(val);return;}//indexsize 尾插if (index size()) {addLast(val);return;}//ListNode cur first;for (int i 0; i index; i) {cur cur.next;}ListNode prev cur.prev;//开始绑定newNode.next cur;newNode.prev prev;prev.next newNode;cur.prev newNode;}//查找是否包含关键字key是否在单链表当中public boolean contains(T key) {if (first null) {return false;}ListNode cur first;while (cur ! null) {if (cur.val.equals(key)) {return true;}cur cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(T key) {if (first null) {return;}//ListNode del first;while (del ! null) {if (del.val.equals(key)) {//删除ListNode pre del.prev;ListNode next del.next;//prenull?if (pre null) {//第一个是keyfirst first.next;return;}if (next null) {//最后一个是keylast last.prev;last.next null;return;}pre.next next;next.prev pre;return;}del del.next;}}//删除所有值为key的节点public void removeAllKey(T key) {if (first null) {return;}//处理前面的keywhile (first.val.equals(key)) {first first.next;if (first null) {return;}}while (last.val.equals(key)) {last last.prev;last.next null;}//ListNode del first;while (del ! null) {if (del.val.equals(key)) {//删除ListNode pre del.prev;ListNode next del.next;//pre.next next;next.prev pre;}del del.next;}}//得到单链表的长度public int size() {int size 0;ListNode cur first;while (cur ! null) {cur cur.next;size;}return size;}public void clear() {while (first ! null) {ListNode next first.next;first.prev first.next null;first next;}last null;}
}今天的内容就到这里感谢老铁们的点赞、收藏、评论~❤
