企业官网建设流程全解析

链表

一、定义

✏️ 链表
在计算机科学中,链表是数据元素的线性集合,其每一个元素都指向下一个元素,元素存储上并不连续

1. 分类

1. 单向链表 : 每个元素只知道其下一个元素是谁

2. 双向链表 : 每个元素知道其上一个元素和下一个元素

3. 循环链表 : 通常的链表尾节点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;/** * 单向链表 */publicclassSinglyLinkedListimplementsIterable<Integer>{privateNodehead;// 头指针// 当某一个内部类使用了外部类的成员变量时,就不能使用static// 如果能加最好加上static/** * 节点类 */privatestaticclassNode{intvalue;Nodenext;publicNode(intvalue,Nodenext){this.value=value;this.next=next;}}/** * 头插法 * @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; }*/// 简化head=newNode(value,head);}/** * 遍历链表 */publicvoidloop1(Consumer<Integer>consumer){Nodecur=head;// 就近原则while(cur!=null){consumer.accept(cur.value);cur=cur.next;}}publicvoidloop2(Consumer<Integer>consumer){for(Nodecur=head;cur!=null;cur=cur.next){consumer.accept(cur.value);}}@OverridepublicIterator<Integer>iterator(){//匿名内部类returnnewIterator<Integer>(){Nodecur=head;@OverridepublicbooleanhasNext(){// 是否有下一个元素returncur!=null;}@OverridepublicIntegernext(){// 返回当前值,并指向下一个元素intv=cur.value;cur=cur.next;returnv;}};}/** * 找到尾节点 */privateNodefindLast(){if(head==null){returnnull;}Nodecur=head;while(cur.next!=null){cur=cur.next;}returncur;}/** * 尾插法 */publicvoidaddLast(intvalue){Nodelast=findLast();if(last==null){addFirst(value);return;}last.next=newNode(value,null);}/** * 根据索引查找指定的节点 * @param index * @return node */privateNodefindNode(intindex){if(head==null){returnnull;}inti=0;for(Nodecur=head;cur!=null;cur=cur.next,i++){if(i==index){returncur;}}returnnull;// 没有找到}/** * 根据索引查找元素的值 * @param index * @return value */publicintget(intindex){Nodecur=findNode(index);if(cur==null){thrownewRuntimeException("未找到指定位置的元素,请检查您传入的索引"+index+"是否合法!");}returncur.value;}/** * 向索引位置插入结点 * @param index * @param value */publicvoidinsert(intindex,intvalue){if(index==0){addFirst(value);}else{Nodecur=findNode(index-1);if(cur==null&&head!=null){thrownewRuntimeException("插入位置不合法");}cur.next=newNode(value,cur.next);}}/** * 删除头节点 */publicvoidremoveFirst(){if(head==null)return;head=head.next;// 旧结点占用的内存会自动释放}/** * 删除指定索引位置的结点 * @param index */publicvoidremove(intindex){if(head==null){thrownewRuntimeException("链表为空!");}if(index==0){removeFirst();return;}Nodecur=findNode(index-1);if(cur==null){thrownewRuntimeException("删除的索引不合法!");}// 删除结点为空也报错Noderemoved=cur.next;if(removed==null){thrownewRuntimeException("删除的索引不合法!");}cur.next=cur.next.next;}}

‍

👻 带头结点的单向链表
带头结点的单向链表的代码实现如下

packagelinked;importjava.util.Iterator;importjava.util.function.Consumer;publicclassSinglyLinkedListSentinelimplementsIterable<Integer>{privateNodehead=newNode(520,null);// 哨兵结点// 当某一个内部类使用了外部类的成员变量时,就不能使用static// 如果能加最好加上static/** * 节点类 */privatestaticclassNode{intvalue;Nodenext;publicNode(intvalue,Nodenext){this.value=value;this.next=next;}}/** * 头插法 * @param value */publicvoidaddFirst(intvalue){insert(0,value);}/** * 遍历链表 */publicvoidloop1(Consumer<Integer>consumer){Nodecur=head.next;// 就近原则while(cur!=null){consumer.accept(cur.value);cur=cur.next;}}publicvoidloop2(Consumer<Integer>consumer){for(Nodecur=head.next;cur!=null;cur=cur.next){consumer.accept(cur.value);}}@OverridepublicIterator<Integer>iterator(){//匿名内部类returnnewIterator<Integer>(){Nodecur=head.next;@OverridepublicbooleanhasNext(){// 是否有下一个元素returncur!=null;}@OverridepublicIntegernext(){// 返回当前值,并指向下一个元素intv=cur.value;cur=cur.next;returnv;}};}/** * 找到尾节点 */privateNodefindLast(){Nodecur=head;while(cur.next!=null){cur=cur.next;}returncur;}/** * 尾插法 */publicvoidaddLast(intvalue){Nodelast=findLast();// 不可能为 nulllast.next=newNode(value,null);}/** * 根据索引查找指定的节点 * @param index * @return node */privateNodefindNode(intindex){inti=-1;for(Nodecur=head;cur!=null;cur=cur.next,i++){if(i==index){returncur;}}returnnull;// 没有找到}/** * 根据索引查找元素的值 * @param index * @return value */publicintget(intindex){Nodecur=findNode(index);if(cur==null){thrownewRuntimeException("未找到指定位置的元素,请检查您传入的索引"+index+"是否合法!");}returncur.value;}/** * 向索引位置插入结点 * @param index * @param value */publicvoidinsert(intindex,intvalue){Nodecur=findNode(index-1);if(cur==null){thrownewRuntimeException("插入位置不合法");}cur.next=newNode(value,cur.next);}/** * 删除头节点 */publicvoidremoveFirst(){remove(0);}/** * 删除指定索引位置的结点 * @param index */publicvoidremove(intindex){Nodecur=findNode(index-1);if(cur==null){thrownewRuntimeException("删除的索引不合法!");}// 删除结点为空也报错Noderemoved=cur.next;if(removed==null){thrownewRuntimeException("删除的索引不合法!");}cur.next=cur.next.next;}}

‍

三、双向链表

未完待续…🥰