赞
踩
在
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
对象
因为这些都是局部变量,方法调用完成之后,局部变量就被回收了
但不代表节点就没人引用了,他们被地址引用,谁引用了他们的地址,谁就引用他们
head == null
的时候,链表就遍历完了。若写成 head.next == null
,则不会打印出最后一个节点的数据head == head. next
即可。head
的位置就不能变,需要一直在首位,所以我们就定义一个 cur
节点,来做 head
的 遍历工作
,head
只负责 站在最前面定位
即可
node
中的数据与其是否为null
是两个独立的概念。在编程和数据结构中,node
通常是一个对象或结构,它包含数据字段和一个或多个指向其他节点的指针或引用。
- 当我们说
node != null
时,我们是在检查node
这个变量是否指向了一个有效的内存地址,即它是否已经被初始化并且分配了内存。node
中的数据字段可以包含任何类型的值,包括null
(如果数据字段的类型允许)。但是,即使数据字段是null
,node
本身仍然可以是一个有效的对象,只是它的数据字段没有包含有用的信息。因此,
node != null
并不表示node
中的数据一定非空或有效。它只表示node
这个变量已经指向了一个在内存中的对象
//遍历链表
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
} System.out.println();
}
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;
}
这里两步的顺序不可以交换,不然就是自己指向自己了
插入节点的时候,一般先绑后面,再插入前面
//头插
public void addFirst(int val) {
ListNode node = new ListNode(val);
node.next = head;
head = node;
}
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;
}
index
的合法性
checkIndex(int index)
方法用来检查 index
的合法性IndexNotLeagalException
index == 0 || index == size();
addFirst()
addLast()
index
的前一个位置
findIndexSubOne(int index)
方法cur
来接收调用方法的返回值cur
就是 index
位置的前一个节点了val
的节点 node
node.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; }
val
值,则返回 true
false
//判断链表中是否包含某个元素
public boolean contains(int val) {
ListNode cur = head;
while(cur != null){
if(cur.val == val){
return true;
}
}
return false;
}
cur.next != null
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; } }
在原有的链表上进行修改
只遍历一遍链表
cur.val == val
prev.next = cur.next
cur = cur.next
prev = cur
cur = 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; } }
回收对象,防止内存浪费
head = null
//清空链表
public void clear() {
head = null;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。