文章目录
前言
在学习顺序表时,我们就了解到虽然它查询和修改元素,根据其下标索引就可以立马实现,但要删除和增加元素,就比较耗时和浪费空间(因为需要移动大量元素)。所以,就有了链表的学习,而链式存储是最常用的动态存储方法。
一、什么是单链表?
链表是用一组任意的存储单元来存放线性表的节点,这组存储单元可以是连续的,也可以是非连续的,甚至可以零散分布在内存的任何位置上。
因此,链表中节点的逻辑顺序和物理顺序不一定相同。
这个节点由两部分组成,一是数据域,用来存放这个节点的值,二是存储下一个节点的地址。
我们可以这样来理解:
链表:逻辑上连续,多个节点采用挂载的方式进行连接,物理上不连续。
我们可以把链表类比做火车,当数据不够时,就新增一节车厢挂载在火车尾。
假设一节车厢只能存储一个元素,要存储5个元素,需要5个车厢,当增加一个元素,就只需要再挂载一个车厢,而不用像顺序表那样,去扩容一倍的空间。
火车结构,都是从头开始遍历,走到火车尾部(报数)
单向遍历:默认从前向后遍历。
二、单链表相关操作(不带虚拟头节点)
准备工作:
1.创建节点类(车厢类,一个车厢存储一个元素)
class Node{
int val;//存储具体数据
Node next;//保存下一个车厢的地址
public Node(int value){
this.val=value;
}
2.创建链表类(火车类–若干个车厢拼接起来,可以将多个车厢连接和断开连接))
具体的增删查改操作都在这个类中实现
public class SingleLinkedList {
private int size;//当前火车中车厢的节点个数(实际上就是具体元素的个数)
private Node head;//指向当前火车的第一个节点
1.插入数据
- 头插法(在链表的头部插入)
public void addFirt(int val){
Node node=new Node(val);//创建一个车厢节点
//判断当前的火车是否为空
if(head==null){
head=node;
}else{
node.next=head;
head=node;
}
size++;
}
- 任意位置插入元素
public void addIndex(int index,int val){
//1.合法性
if(index<0||index>size){
System.err.println("add index illegal!");
return;
}
//头插法
if(index==0){
addFirst(val);
return;
}
//插入元素
Node node=new Node(val);
//需要找到待插入位置的前驱--从头开始走index-1步
Node prev=head;
for (int i = 0; i <index-1 ; i++) {
prev=prev.next;
}
//此时prev指向待插入位置的前驱节点
node.next=prev.next;
prev.next=node;
size++;
}
- 尾部插入元素
public void addLast(int val){
addIndex(size,val);
}
public int get(int index){
if(rangeCheck(index)){
//index合法,从头节点开始遍历链表,走到index位置
Node node=head;
//规定了node节点走的步数
for (int i = 0; i <index; i++) {//注意边界
node=node.next;
}
return node.val;
}else{
System.err.println("get index illegal!");
return -1;
}
}
2.查询数据
判断当前链表中是否包含值为val的节点
public boolean contains(int val){
for (Node temp=head;temp!=null;temp=temp.next){
if(temp.val==val){
return true;
}
}
return false;
}
3.修改元素
将链表中索引为index的节点值改为newVal,并返回原来旧节点的值
public int set(int index,int newVal){
if(rangeCheck(index)){
Node node=head;
for (int i = 0; i < index; i++) {
node=node.next;
}
int oldVal=node.val;
node.val=newVal;
return oldVal;//改成功后返回旧的值
}
else{
System.err.println("set index illegal!");
return -1;
}
}
注意:查和改都不能走到size.
4.删除元素
- 删除任意元素节点
引入临时变量存储原先head节点的地址,如果用头节点来遍历,最后会丢失头节点。
public void removeIndex(int index){
//1.判断合法性
if(rangeCheck(index)){
if(index==0){
//删除头节点
Node temp=head;
head=head.next;
temp.next=null;
size--;
}else{
//inde为中间位置,然后找待删除位置的前驱
Node prev=head;
for (int i = 0; i < index-1; i++) {
prev=prev.next;
}
//待删除节点
Node cur=prev.next;
prev.next=cur.next;
cur.next=null;
size--;
}
}else{
System.err.println("remove index illegal!");
}
}
如果只写head=head.next,而不写其他两个,则只是保证了原先的头节点访问不到而已,但头节点是实实在在存在的,依旧挂在链表上。
2.删除第一个元素
public void removeFirst(){
removeIndex(0);
}
3.删除最后一个元素
public void removeLast() {
removeIndex(size - 1);
}
4.删除第一个值为value的节点
public void removeValueOnce(int val){
//遍历链表,找到值为value的节点,然后删除(正常删除都需要找到前驱,只有头节点没有前驱)
if(head!=null&&head.val==val){
//头节点就是待删除的节点
Node temp=head;
head=head.next;
temp.next=null;
size--;
}else{
//此时head一定不是待删除的节点
Node prev=head;
//判断前驱的下一个节点值是否等于value
while(prev.next!=null){//看你取值用的是哪个引用,就判断哪个引用不为空
if(prev.next.val==val){
Node cur=prev.next;
prev.next=cur.next;
cur.next=null;
size--;
return;
}
//prev不是待删除节点的前驱,prev向后移动
prev=prev.next;
}
}
}
5.删除所有值为val的节点
public void removeValueAll(int val){
//判断头节点是否是待删除节点
while (head!=null&&head.val==val){
head=head.next;
size--;
}
if(head==null){
//此时链表中的值全是val,及删空了链表
return;
}else{
//此时head一定不是待删除节点,并且链表中还有节点
Node prev=head;
while(prev.next!=null){
if(prev.next.val==val){
Node cur=prev.next;
prev.next=cur.next;
cur.next=null;
size--;
}else{
prev=prev.next;//确保prev.next不是待删除的节点时才能移动prev指向
}
}
}
}
关键点:
- 因为要通过head引用取得val值–head.val,所以为了避免空指针异常,循环中必须要满足head!=null。
- 只有当确保prev.next不是待删除的节点时才能移动prev=prev.next;指向
prev一定不是待删除的节点
总结
在单链表的插入与删除,都需要找到前驱节点(只有头节点没有前驱,因此需要特殊处理),那么找到前驱便找到插入与删除的钥匙。
优点:1.对链表进行增加元素时,只要内存够用,就不会发生溢出。
2.增加和删除元素时,会比顺序表更方便。
缺点:查寻和更新元素需要从头向后遍历,会比较耗时。