网站建设网站形象,滨州网站建设,wordpress更改ico,游戏怎么做充值网站在 ArrayList 任意位置插入或者删除元素时#xff0c;就需要将后序元素整体往前或者往后搬移#xff0c;时间复杂度为 O(n)#xff0c;效率比较低#xff0c;因此 ArrayList 不适合做任意位置插入和删除比较多的场景。因此#xff1a;java 集合中又引入了 LinkedList… 在 ArrayList 任意位置插入或者删除元素时就需要将后序元素整体往前或者往后搬移时间复杂度为 O(n)效率比较低因此 ArrayList 不适合做任意位置插入和删除比较多的场景。因此java 集合中又引入了 LinkedList即链表结构。 概念
顺序表是物理上连续逻辑上也是连续的 链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链表是由一个一个的节点组织起来的整体的组织就叫链表 注意
从上图可看出链式结构在逻辑上是连续的但在物理上不一定连续现实中的节点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续 节点可以认为是节点对象对象里面有两个节点属性val 用来存储数据next 用来存储下一个节点的地址 分类
链表
单向/双向带头/不带头: 带头就是带一个头节点头结点的数据域可以不存储任何信息也可以用来存储一些附加信息如链表的长度等。 循环/不循环 循环就是将最后一个节点里面地址改为第一个节点的地址 链表结构
单向带头循环单向带头非循环单向不带头循环单向不带头非循环重点双向带头循环双向带头非循环双向不带头循环双向不带头非循环重点 链表的实现
链表的构造
节点的构造和连接 如何构造节点 当一个事物的内部还有一个部分需要一个完整的结构进行描述而这个内部的完整的结构又只为外部食物提供服务那么这个内部类的完整结构最好使用 内部类因为链表是由若干节点组成而节点又是一个完整的结构所以将节点定义为内部类。其最少有两个域一个是数值域一个是 next域且 next 的类型为节点类型最后对节点进行构造只需要实例化这个内部类的对象即可实例化出来的对象便是节点
class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val val; }
}public ListNode head; public void createList() { ListNode node1 new ListNode(12); ListNode node2 new ListNode(23); ListNode node3 new ListNode(34); ListNode node4 new ListNode(45); ListNode node5 new ListNode(56);
}如何让它与第一个节点相关联 通过访问 node1 存储地址的变量 next将其的值赋为下一个节点的地址以此类推最后让头节点指向第一个节点 node1
node1.next node2;
node2.next node3;
node3.next node4;
node4.next node5; this.head node1;当 createList 方法走完之后实例化的各个节点对象就没有了只保留了一个 head 对象 因为这些都是局部变量方法调用完成之后局部变量就被回收了 但不代表节点就没人引用了他们被地址引用谁引用了他们的地址谁就引用他们 链表的功能
void display()——遍历链表
当 head null 的时候链表就遍历完了。若写成 head.next null则不会打印出最后一个节点的数据要从第一个节点走到第二个节点只需要 head head. next 即可。但若想完成多次打印head 的位置就不能变需要一直在首位所以我们就定义一个 cur 节点来做 head 的 遍历工作head 只负责 站在最前面定位 即可 node 中的数据与其是否为 null 是两个独立的概念。在编程和数据结构中node 通常是一个对象或结构它包含数据字段和一个或多个指向其他节点的指针或引用。 当我们说 node ! null 时我们是在检查 node 这个变量是否指向了一个有效的内存地址即它是否已经被初始化并且分配了内存。node 中的数据字段可以包含任何类型的值包括 null如果数据字段的类型允许。但是即使数据字段是 nullnode 本身仍然可以是一个有效的对象只是它的数据字段没有包含有用的信息。 因此node ! null 并不表示 node 中的数据一定非空或有效。它只表示 node 这个变量已经指向了一个在内存中的对象 //遍历链表
public void display() { ListNode cur head; while (cur ! null) { System.out.print(cur.val ); cur cur.next; } System.out.println();
}int size()——求链表长度
定义一个 count 变量用来记录 cur 向后走的次数每向后走一步count 不能写成cur.next ! null因为最后一个节点的 next 为空若是这样判断的话最后一个节点就不会进循环了就会少算一个 //计算链表长度
public int size() { int count 0; ListNode cur head; while (cur ! null) { count; cur cur.next; } return count;
}void addFirst(int val)——头插法
将此时头结点的地址传给 node 的 next 变量将头节点前移到 node 的地方 这里两步的顺序不可以交换不然就是自己指向自己了 插入节点的时候一般先绑后面再插入前面 //头插
public void addFirst(int val) { ListNode node new ListNode(val); node.next head; head node;
}void addLast(int val)——尾插法
为了避免产生空指针异常报错我们先对 head null 的情况进行讨论 若头节点为空则 head node;记得加上 return否则程序会继续执行下去 若链表不为空找到链表的尾巴 当 cur. next null 时cur 指向的就是尾巴 最后让 head.next node; 即可 //尾插
public void addLast(int val) { ListNode node new ListNode(val); if (head null) { head node; return; } ListNode cur head; while (cur.next ! null) { cur cur.next; } cur.next node;
}void addIndex(int index, int val)——在任意位置插入
判断 index 的合法性 定义一个 checkIndex(int index) 方法用来检查 index 的合法性若不合法则抛出一个自定义异常IndexNotLeagalException index 0 || index size(); 前者相当于是头插直接调用 addFirst()后者相当于是尾插直接调用 addLast() 找到 index 的前一个位置 创建一个 findIndexSubOne(int index) 方法创建一个节点 cur 来接收调用方法的返回值最后 cur 就是 index 位置的前一个节点了 进行连接 实例化一个所带数据为 val 的节点 nodenode.next cur.next;cur.next node; //在任意位置插入
public void addIndex(int index, int val) { //1. 判断index的合法性 try { checkIndex(index); } catch (IndexNotLegalException e) { e.printStackTrace(); } //2. index 0 || index size() if(index 0){ addFirst(val); return; } else if(index this.size()){ addLast(val); return; } //3. 找到 index 的前一个位置 ListNode cur findIndexSubOne(index); //4. 进行连接 ListNode node new ListNode(val); node.next cur.next; cur.next node;
} //用来检查输入的 index 是否合法的方法
public void checkIndex(int index) { if(index 0 || index size()){ //若不合法则抛出一个异常throw new IndexNotLegalException(index位置不合法); }
} //用来找到 index 前一位对应的节点的函数
private ListNode findIndexSubOne(int index) { ListNode cur head; for (int i 0; i index - 1; i) { cur cur.next; } return cur;
}boolean contains(int val)——链表中是否包含某个元素
遍历链表若能在链表元素中找到 val 值则返回 true否则返回 false //判断链表中是否包含某个元素
public boolean contains(int val) { ListNode cur head; while(cur ! null){ if(cur.val val){ return true; } } return false;
}void remove(int key)——删除第一次出现的关键字的节点
首先判断是否为空链表遍历链表 循环条件为cur.next ! null 找到 val 值的前一个节点 cur 当 cur.next.val val 时找到目标 进行删除 找到之后将其创建为 del 节点cur.next del.next 或者 cur.next cur.next.next看表达式可知删除的判断是从第二个元素开始的无法对第一个元素进行判断所以需要针对第一个元素再加上一个删除判断head.val val //删除第一次出现的关键字的节点
public void remove(int val) { //链表为空 if(head null){ return; } //当第一个元素就为 val if(head.val val){ head head.next; return; } ListNode cur head; while(cur.next ! null){ if(cur.next.val val){ ListNode del cur.next; cur.next del.next; } cur cur.next; }
}void removeAll(int val)——删除所有出现的关键字的节点
在原有的链表上进行修改 只遍历一遍链表
定义两个引用变量 cur 代表当前需要删除的节点prev 代表当前需要删除节点的前驱
若 cur.val val prev.next cur.nextcur cur.next 否则 prev curcur cur.next 处理头节点 //删除所有出现的关键字节点
public void removeAll(int val) { //1. 判空 if (head null) { return; } //2. 定义 prev 和 cur ListNode prev head; ListNode cur head.next; //3. 开始判断并删除 while (cur ! null) { if (cur.val val) { prev.next cur.next; } else { prev cur; } cur cur.next; } //4. 处理头结点 if (head.val val) { head head.next; }
}void clear()——清空
回收对象防止内存浪费 head null //清空链表
public void clear() { head null;
}
