东莞技术网站建设,合肥seo搜索优化,网络工程师岗位职责,东莞服装网站建设链表#xff08;二#xff09; 文章目录 链表#xff08;二#xff09;00 引入01 类的搭建02 得到链表的长度03 打印链表04 查找是否包含关键字key是否在链表当中05 头插法06 尾插法07 任意位置插入08 删除关键字为key的节点09 删除所有值为key的节点10 清空11 LinkedList常…链表二 文章目录 链表二00 引入01 类的搭建02 得到链表的长度03 打印链表04 查找是否包含关键字key是否在链表当中05 头插法06 尾插法07 任意位置插入08 删除关键字为key的节点09 删除所有值为key的节点10 清空11 LinkedList常规一些操作12 ArrayList与LinkedList的区别 00 引入
衔接上文单链表相较于本篇将要讲的双链表单链表有以下弱势
难以反向遍历由于单链表只包含一个指针即指向下一个节点的指针无法直接访问前一个节点。因此在单链表中反向遍历需要从头节点开始顺序遍历到目标节点效率相对较低。难以在任意位置快速插入和删除在双链表中可以通过两个指针的操作快速定位到目标节点的前后节点从而在O(1)时间复杂度内进行插入和删除操作。而在单链表中为了插入或删除目标节点需要先找到目标节点的前一个节点并修改其指针指向操作相对复杂时间复杂度为O(n)。难以在尾部追加节点由于单链表只有一个指针指向下一个节点如果要在单链表的尾部追加节点就需要遍历整个链表找到尾节点然后进行操作。而双链表在尾部追加节点只需要修改尾节点的指针操作更加简单和高效。 那么接下来就让我们来实现一下非循环双向链表。
双向链表也叫双链表是链表的一种它的每个数据结点中都有两个指针分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。
01 类的搭建 示例代码如下
static class ListNode{private int val;private ListNode prev;private ListNode next;public ListNode(int val) {this.val val;}}public ListNode head;//定义双向链表的头节点public ListNode last;//定义双向链表的尾巴02 得到链表的长度
这个其实就是遍历一下链表和单链表的操作没有区别。
示例代码如下
//得到单链表的长度public int size(){ListNode cur this.head;int count 0;while(cur ! null){count;cur cur.next;}return count;}03 打印链表
原则如02操作。
示例代码如下
public void display(){ListNode cur this.head;while(cur ! null){System.out.println(cur -);cur cur.next;}System.out.println(null);}04 查找是否包含关键字key是否在链表当中
原则如02 03操作
示例代码如下
//查找是否包含关键字key是否在链表当中public boolean contains(int key){ListNode cur this.head;while(cur ! null){if (cur.val key){return true;}cur cur.next;}return false;}05 头插法
注意考虑点:
考虑空链表的情况如果链表为空即没有任何节点那么插入的节点将成为新的头节点。在这种情况下需要特殊处理头节点的前后指针。更新头节点的前驱指针在头插法中插入的节点将成为新的头节点所以需要更新原头节点的前驱指针让它指向新的头节点。更新新头节点的后继指针插入的节点作为新的头节点它的后继指针需要指向原来的头节点以连接链表的其他节点。 示例代码如下
//头插法public void addFirst(int data){ListNode node new ListNode(data);if(head null){head node;last node;}else {node.next head;head.prev node;head node;}}06 尾插法
注意点
考虑空链表的情况如果链表为空即没有任何节点那么插入的节点将成为新的头节点。在这种情况下需要特殊处理头节点的前后指针。更新尾节点的后继指针在尾插法中插入的节点将成为新的尾节点所以需要更新原尾节点的后继指针让它指向新的尾节点。更新新尾节点的前驱指针插入的节点作为新的尾节点它的前驱指针需要指向原来的尾节点以连接链表的其他节点。 示例代码
//尾插法public void addLast(int data){ListNode node new ListNode(data);if (head null){head node;last node;}else {last.next node;node.prev last;last node;}}07 任意位置插入
注意点
判断插入位置是否合法首先要确保插入的位置在链表的长度范围内即在 0 到链表长度的范围之间。更新插入节点的前驱指针和后继指针在进行任意位置插入时需要更新插入节点的前驱指针和后继指针使其正确指向前一个节点和后一个节点。更新前后节点的指针需要更新前一个节点和后一个节点的后继指针和前驱指针让它们正确地连接到插入节点上。 示例代码
//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){checkIndex(index);if(index 0){addFirst(data);return;}else if (index size()){addLast(data);return;}ListNode node new ListNode(data);ListNode cur head;while(index ! 0){cur cur.next;index--;}node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;}private void checkIndex(int index){if (index 0 || index size()){throw new IndexOutOfException(index 不合法);}}08 删除关键字为key的节点
查找要删除的节点首先需要在双链表中找到第一次出现关键字为key的节点。遍历链表逐个比较节点的值直到找到目标节点或遍历到链表末尾。更新前后节点的指针找到目标节点后需要更新前一个节点和后一个节点的后继指针和前驱指针让它们正确地连接起来。处理删除头节点的情况如果需要删除头节点需要特殊处理。即使要删除的节点是头节点也要正确更新头指针。 示例代码
//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur head;while (cur ! null) {if (cur.val key) {//删除头节点if (cur head) {head head.next;if (head ! null) {//考虑只有一个节点的情况head.prev null;}else {last null;}} else {//删除中间节点以及尾巴节点if (cur.next ! null) {//中间节点cur.prev.next cur.next;cur.next.prev cur.prev;} else {//尾巴节点cur.prev.next cur.next;last last.prev;}}return;} else {cur cur.next;}}}09 删除所有值为key的节点
这个与08其实大差不差。
示例代码
//删除所有值为key的节点public void removeAllKey(int key){ListNode cur head;while (cur ! null) {if (cur.val key) {//删除头节点if (cur head) {head head.next;if (head ! null) {//考虑只有一个节点的情况head.prev null;}else {last null;}} else {//删除中间节点以及尾巴节点if (cur.next ! null) {//中间节点cur.prev.next cur.next;cur.next.prev cur.prev;} else {//尾巴节点cur.prev.next cur.next;last last.prev;}}//return;//区别所在cur cur.next;} else {cur cur.next;}}}唯一的区别就是在寻找出第一个关键字key之后继续往后走cur cur.next继续删直到删完为止。
10 清空
使用一个循环来遍历双链表中的每个节点并且可以选择释放每个节点所占用的内存。最后将头节点指针设置为null以清空链表。
public void clear(){ListNode cur head;while(cur ! null){ListNode curNext cur.next;cur.prev null;cur.next null;cur curNext;}head null;last null;}11 LinkedList常规一些操作
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;/*** date 2023/8/16*/
public class Test {public static void main(String[] args) {ListInteger list new LinkedList();list.add(1);list.add(1);list.add(1);list.add(1);System.out.println(list);for(int x : list) {System.out.println(x);}System.out.println();ListIteratorInteger it list.listIterator();while (it.hasNext()) {System.out.print(it.next() );}System.out.println();System.out.println();ListIteratorInteger it2 list.listIterator(list.size());while (it2.hasPrevious()) {System.out.print(it2.previous() );}System.out.println();}
}12 ArrayList与LinkedList的区别
内部实现ArrayList是基于数组实现的动态数组而LinkedList是基于双向链表实现的。因此在插入或删除元素时ArrayList需要移动数组中的元素而LinkedList只需要改变节点的指针。访问效率由于ArrayList是基于数组实现的它可以通过索引直接访问元素因此在随机访问元素时效率较高。而LinkedList需要从头节点或尾节点开始遍历链表因此随机访问的效率较低。插入和删除效率在插入或删除元素时ArrayList需要移动元素来保持数组的连续性因而在特定位置的插入和删除操作的效率较低。而LinkedList只需要改变节点的指针因此在特定位置的插入和删除操作的效率较高。空间占用由于ArrayList是基于数组实现的它需要一段连续的内存空间来存储元素因此在使用期间其大小是固定的。而LinkedList每个节点都需要额外的空间来存储前后节点的指针因此在空间占用方面相对较大。
综上所述ArrayList适用于有频繁的随机访问操作和插入/删除较少的场景而LinkedList适用于有频繁的插入/删除操作和随机访问较少的场景。根据具体的应用场景和需求可以选择合适的集合类。 那么至此关于链表的一些总结到此暂时完结撒花接下来会学习栈和队列MySQL以及不定时的算法总结其实有额外时间的话准备详细聊聊C中的动态内存管理以及结构体之类的知识。
