链表的语法详解

链表一、定义✏️ 链表在计算机科学中,链表是数据元素的线性集合,其每一个元素都指向下一个元素,元素存储上并不连续1. 分类单向链表 : 每个元素只知道其下一个元素是谁双向链表 : 每个元素知道其上一个元素和下一个元素循环链表 : 通常的链表尾节点tail指向的都是null,而循环链表的tail指向的是头节点head 哨兵节点不存储数据,通常用作头尾,用来简化边界的判断‍2. 性能随机访问 : 根据index查找,时间复杂度O(n)插入或删除 :起始位置 : O(1)结束位置 : 如果已知尾节点是O(1),不知道尾节点是O(n)中间位置 : 根据index查找时间 O(1)‍二、单向链表 不带头结点的单向链表不带头结点的单向链表的代码实现如下packagelinked;importjava.util.Iterator;importjava.util.function.Consumer;/** * 单向链表 */publicclassSinglyLinkedListimplementsIterableInteger{privateNodehead;// 头指针// 当某一个内部类使用了外部类的成员变量时,就不能使用static// 如果能加最好加上static/** * 节点类 */privatestaticclassNode{intvalue;Nodenext;publicNode(intvalue,Nodenext){this.valuevalue;this.nextnext;}}/** * 头插法 * param value */publicvoidaddFirst(intvalue){/*// 1.链表为空 if(head null){ head new Node(value,null); }else{ // 2.链表非空 Node newNode new Node(value,null); newNode.next head; head newNode; }*/// 简化headnewNode(value,head);}/** * 遍历链表 */publicvoidloop1(ConsumerIntegerconsumer){Nodecurhead;// 就近原则while(cur!null){consumer.accept(cur.value);curcur.next;}}publicvoidloop2(ConsumerIntegerconsumer){for(Nodecurhead;cur!null;curcur.next){consumer.accept(cur.value);}}OverridepublicIteratorIntegeriterator(){//匿名内部类returnnewIteratorInteger(){Nodecurhead;OverridepublicbooleanhasNext(){// 是否有下一个元素returncur!null;}OverridepublicIntegernext(){// 返回当前值,并指向下一个元素intvcur.value;curcur.next;returnv;}};}/** * 找到尾节点 */privateNodefindLast(){if(headnull){returnnull;}Nodecurhead;while(cur.next!null){curcur.next;}returncur;}/** * 尾插法 */publicvoidaddLast(intvalue){NodelastfindLast();if(lastnull){addFirst(value);return;}last.nextnewNode(value,null);}/** * 根据索引查找指定的节点 * param index * return node */privateNodefindNode(intindex){if(headnull){returnnull;}inti0;for(Nodecurhead;cur!null;curcur.next,i){if(iindex){returncur;}}returnnull;// 没有找到}/** * 根据索引查找元素的值 * param index * return value */publicintget(intindex){NodecurfindNode(index);if(curnull){thrownewRuntimeException(未找到指定位置的元素,请检查您传入的索引index是否合法!);}returncur.value;}/** * 向索引位置插入结点 * param index * param value */publicvoidinsert(intindex,intvalue){if(index0){addFirst(value);}else{NodecurfindNode(index-1);if(curnullhead!null){thrownewRuntimeException(插入位置不合法);}cur.nextnewNode(value,cur.next);}}/** * 删除头节点 */publicvoidremoveFirst(){if(headnull)return;headhead.next;// 旧结点占用的内存会自动释放}/** * 删除指定索引位置的结点 * param index */publicvoidremove(intindex){if(headnull){thrownewRuntimeException(链表为空!);}if(index0){removeFirst();return;}NodecurfindNode(index-1);if(curnull){thrownewRuntimeException(删除的索引不合法!);}// 删除结点为空也报错Noderemovedcur.next;if(removednull){thrownewRuntimeException(删除的索引不合法!);}cur.nextcur.next.next;}}‍ 带头结点的单向链表带头结点的单向链表的代码实现如下packagelinked;importjava.util.Iterator;importjava.util.function.Consumer;publicclassSinglyLinkedListSentinelimplementsIterableInteger{privateNodeheadnewNode(520,null);// 哨兵结点// 当某一个内部类使用了外部类的成员变量时,就不能使用static// 如果能加最好加上static/** * 节点类 */privatestaticclassNode{intvalue;Nodenext;publicNode(intvalue,Nodenext){this.valuevalue;this.nextnext;}}/** * 头插法 * param value */publicvoidaddFirst(intvalue){insert(0,value);}/** * 遍历链表 */publicvoidloop1(ConsumerIntegerconsumer){Nodecurhead.next;// 就近原则while(cur!null){consumer.accept(cur.value);curcur.next;}}publicvoidloop2(ConsumerIntegerconsumer){for(Nodecurhead.next;cur!null;curcur.next){consumer.accept(cur.value);}}OverridepublicIteratorIntegeriterator(){//匿名内部类returnnewIteratorInteger(){Nodecurhead.next;OverridepublicbooleanhasNext(){// 是否有下一个元素returncur!null;}OverridepublicIntegernext(){// 返回当前值,并指向下一个元素intvcur.value;curcur.next;returnv;}};}/** * 找到尾节点 */privateNodefindLast(){Nodecurhead;while(cur.next!null){curcur.next;}returncur;}/** * 尾插法 */publicvoidaddLast(intvalue){NodelastfindLast();// 不可能为 nulllast.nextnewNode(value,null);}/** * 根据索引查找指定的节点 * param index * return node */privateNodefindNode(intindex){inti-1;for(Nodecurhead;cur!null;curcur.next,i){if(iindex){returncur;}}returnnull;// 没有找到}/** * 根据索引查找元素的值 * param index * return value */publicintget(intindex){NodecurfindNode(index);if(curnull){thrownewRuntimeException(未找到指定位置的元素,请检查您传入的索引index是否合法!);}returncur.value;}/** * 向索引位置插入结点 * param index * param value */publicvoidinsert(intindex,intvalue){NodecurfindNode(index-1);if(curnull){thrownewRuntimeException(插入位置不合法);}cur.nextnewNode(value,cur.next);}/** * 删除头节点 */publicvoidremoveFirst(){remove(0);}/** * 删除指定索引位置的结点 * param index */publicvoidremove(intindex){NodecurfindNode(index-1);if(curnull){thrownewRuntimeException(删除的索引不合法!);}// 删除结点为空也报错Noderemovedcur.next;if(removednull){thrownewRuntimeException(删除的索引不合法!);}cur.nextcur.next.next;}}‍三、双向链表未完待续…