赞
踩
上篇博客中介绍了顺序表有关的知识,我们知道顺序表增加,删除某个元素都需要移动其他元素,增加了时间复杂度;顺序表空间不够用又需要我们进行扩容,导致可能造成空间上的浪费,增加了空间复杂度,因此有必要优化顺序表,因此我们引入链表的概念。
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
虽然有这么多的链表的结构,但是我们重点掌握两种:
无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
说明:prev和next存储的都是引用(地址)
在无头单向非循环链表中,我们将每个元素叫做节点,因此,我们将节点封装成一个类:
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
类中有两个成员变量,val(值),next(下一个节点的地址),构造方法是将val值赋值给该对象的val,这就是一个节点,我们将若干个节点连起来就形成了链表
我们以枚举5个节点为例:
public class MyLinkedList {
public ListNode head;//链表的头引用
public void createList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
}
我们实例化5个对象listNode1、listNode2、listNode3、listNode4、listNode5因为构造方法的实现因此,每个节点依次赋值为12,23,34,45,56。
但是每个节点的next(成员变量(next)没赋值,所以为null)为null,并没有建立起联系所以,我们需要将这5个节点建立起联系。listNode1.next = listNode2;listNode2.next=listNode3;listNode3.next=listNode4;listNode4.next = listNode5;就是将listNode2的地址给listNode1的next,同理listNode3,listNode4,listNode5也是如此。因此建立起联系图就变成了:
为了方便标记,我们将第一个节点赋给head的节点(并不是有头的head节点)。因此,简单的链表结构就形成了。
//打印无头单向非循环链表
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
实例化cur引用,指向head节点,只需要cur不等于0时,打印出cur的val值,并将cur的next赋值给cur,就实现了cur往后移动,因为节点的next存储的是下一个节点的地址,只需要将cur的next值赋值给cur,cur就指向了下一个节点。
//查找是否包含关键字
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
} else {
cur = cur.next;
}
}
return false;
}
同样的实例化cur节点,指向head节点,前期条件是cur并不是null,用cur遍历整个链表,如果cur的val与key相等返回true,否则cur移动到下一个节点,一直到最后一个节点(最后一个节点的next值为null),将null赋值给cur,所以cur不满足cur != null的条件,退出循环,返回false。
//获取链表的长度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
定义一个计数器count,只要cur移动一次,count就++,最后返回count的值。
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;//包含了head为null的情况
// if (this.head == null) {
// this.head = node;
// } else {
// node.next = head;
// head = node;
// }
}
插入一个节点有三种方式:头插法,尾插法,任意位置插入,我们先画图理解一下头插法的过程。
首先有一个链表,我们实例化一个节点node( ListNode node = new ListNode(data);),假设地址为0x678,此时该节点的next为null,那么如果用头插法我们只需要将第一个节点的地址0x123给node的next,并将头head指向node节点就可以完成。就像这样:
当然我们还有考虑当head==null时的情况,即链表没有一个节点,我们发现第一步还是要实例化一个节点,然后把head的值给node的next,此时head为null,因此node的next也为null,在将node的地址赋值给head(head指向node),因此上述的代码包含了head=null的情况,因此可以简化代码。
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
} else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
尾插法相对于头插法就要难一点,因为要找到最后一个节点在进行插入的操作,我们以图为例:
还是以上一个例子为例,首先我们需要找到,最后一个节点,因此我们实例化一个cur节点,这个节点一开始赋值为头,当cur.next!=null时说明此时不是该链表的最后一个节点,往后移动(cur=cur.next),移动到最后一个节点时,我们需要将node的地址赋值给cur.next,完成节点的链接,像这样:
当然,我们需要将head为null的情况考虑在内,当head为null时,如果是将cur.next = node;是不行的,因为只有一个节点,那么该节点的next应为null,而不是node的值,因此我们需要将head为null的情况单独考虑。也就是head为null时,将node赋给head即可。
为了方便,我们将寻找节点的函数单独写成一个方法:
//找到index-1位置节点的地址
public ListNode findIndex(int index) {
ListNode cur = this.head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int data) { if (index < 0 || index > size()) { System.out.println("index位置不合法"); return; } if (index == 0) { addFirst(data); return; } if (index == size()) { addLast(data); return; } ListNode cur = findIndex(index); ListNode node = new ListNode(data); node.next = cur.next; cur.next = node; }
我们将第一个节点设为下标为0,我们画图为例:
我们将node插进下标为2和3之间,首先我们需要用cur找到下标为2的节点,然后将cur的next赋值给node的next,再将node赋值给cur的next。像这样:
但是我们需要找到下标为2的位置,那么我们就可用findIndex()方法,首先我们需要实例化一个cur的节点(指向head节点)(如果要插进下标为3的位置那么cur的下标是为2),比如index为3,因为index-1!=0,那么cur往后移一个位置,并且index–;以此类推,直到index-1==0,返回cur的值。这个问题也解决了,我们还需要考虑,index的取值是否合法,首先index不能为负数,并且index不能大于链表的长度,当然我们插入的位置都是介于两个节点之间,我们还需要考虑插入头位置和尾位置,所以我们直接使用上面所写的头插法和尾插法就可以了。
为了方便,我们将寻找关键字的前驱写成单独的方法:
//找到要删除的关键字的前驱
public ListNode searchPerv(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//删除第一次出现关键字为key的节点 public void remove(int key) { if (this.head == null) { System.out.println("单链表为null,不能删除!"); return; } if (this.head.val == key) { this.head = this.head.next; return; } ListNode cur = searchPerv(key); if (cur == null) { System.out.println("没有找到你要删除的节点!"); return; } ListNode del = cur.next; cur.next = del.next; }
我们画图为例:
假设我们要删除第一个val为34的节点,那么我们需要将cur移动到该节点的前一个节点,然后再实例化一个节点del,这个节点为cur的next,也就是说cur是val值为23这个节点,而del是val为34这个节点,我们删除del这个节点,我们将cur的next赋值成del的next,也就是将0x456(index.next),赋值给0x345(cur.next)。像这样:
但是如何找到val值为34的前一个节点呢?这就用到searchPerv()方法,首先实例化cur节点(指向head),当cur的next不为null时,判断cur.next.val为不为key(要删除的val值),如果相等,返回cur,不过不等,则cur往后移动,直到cur.next为null为止,返回null。解决了找删除关键字为前一个节点的问题,我们还需要注意单链表是否为null,当head为null时,打印相应的提醒,当searchPerv()返回值为null时,证明没有找到要删除的节点。还有最重要的一点就是,如果head就是我要删除的节点,我们上述的方法是寻找删除节点的前一个节点,但是head节点并没有前一个节点,因此我们还需要单独考虑,如果head的val值为key,那么我们将head的next赋值给head,实现了head的往后移动一个节点。
有同学说一直用remove()方法删除直到遍历完整个链表不就可以了嘛?是的这样的确可以,拿有没有更为简便的方法呢?当然有:
//删除所有为key的节点 public ListNode removeAllKey(int key) { if (this.head == null) { return null; } ListNode prev = this.head; ListNode cur = this.head.next; while (cur != null) { if (cur.val == key) { prev.next = cur.next; cur = cur.next; } else { cur = cur.next; prev = prev.next; } } if (this.head.val == key) { this.head = this.head.next; } return this.head; }
我们来看图:
我们先实例化两个节点(prev指向head,cur指向head的下一个节点),如果我们要删除key为23,那么,如果cur的val为23,那么将cur的next赋值给prev的next,这样cur这个节点就被删除了,cur往下移动(cur=cur.next),如果cur的val值不等于key,那么cur和prev都往下一个移动,直到cur为null跳出循环,比如删除第一个23,应该是这样的:
当然,我们还需要考虑链表没有节点的时候和head的val值是我们想要删除的节点,处理的过程还是删除单个key的处理。因此代码大致相同。
//清空单链表
public void clear() {
// this.head = null;暴力处理
while (this.head != null) {
ListNode curNext = head.next;
this.head.next = null;
this.head = curNext
}
}
清空单链表有两种方法,一种是暴力处理,一种是相对柔和的处理方式,暴力处理是将head置为null值,那么整个链表就空了,也就是this.head = null即可,另一种相对来说麻烦一点,就是一个一个节点遍历,将所有节点的next都置为null(对于链表清空,只要没有东西引用他,操作系统就会回收,并不需要将val置为0),但是有一个问题,如果我们将head的next置为null,那么如何找到head的下一个节点,因此我们要借助实例化curNext节点(指向head的下一个节点),当指控head的next后,将curNext赋值给head,实现了head往后移动,直到head为null,清空了整个链表。
class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; } } public class MyLinkedList { public ListNode head;//链表的头引用 //打印无头单向非循环链表 public void display() { ListNode cur = this.head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } //查找是否包含关键字 public boolean contains(int key) { ListNode cur = this.head; while (cur != null) { if (cur.val == key) { return true; } else { cur = cur.next; } } return false; } //获取链表的长度 public int size() { int count = 0; ListNode cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } //头插法 public void addFirst(int data) { ListNode node = new ListNode(data); node.next = this.head; this.head = node;//包含了head为null的情况 // if (this.head == null) { // this.head = node; // } else { // node.next = head; // head = node; // } } //尾插法 public void addLast(int data) { ListNode node = new ListNode(data); if (this.head == null) { this.head = node; } else { ListNode cur = this.head; while (cur.next != null) { cur = cur.next; } cur.next = node; } } //找到index-1位置节点的地址 public ListNode findIndex(int index) { ListNode cur = this.head; while (index - 1 != 0) { cur = cur.next; index--; } return cur; } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int data) { if (index < 0 || index > size()) { System.out.println("index位置不合法"); return; } if (index == 0) { addFirst(data); return; } if (index == size()) { addLast(data); return; } ListNode cur = findIndex(index); ListNode node = new ListNode(data); node.next = cur.next; cur.next = node; } //找到要删除的关键字的前驱 public ListNode searchPerv(int key) { ListNode cur = this.head; while (cur.next != null) { if (cur.next.val == key) { return cur; } cur = cur.next; } return null; } //删除第一次出现关键字为key的节点 public void remove(int key) { if (this.head == null) { System.out.println("单链表为null,不能删除!"); return; } if (this.head.val == key) { this.head = this.head.next; return; } ListNode cur = searchPerv(key); if (cur == null) { System.out.println("没有找到你要删除的节点!"); return; } ListNode del = cur.next; cur.next = del.next; } //删除所有为key的节点 public ListNode removeAllKey(int key) { if (this.head == null) { return null; } ListNode prev = this.head; ListNode cur = this.head.next; while (cur != null) { if (cur.val == key) { prev.next = cur.next; cur = cur.next; } else { cur = cur.next; prev = prev.next; } } if (this.head.val == key) { this.head = this.head.next; } return this.head; } //清空单链表 public void clear() { this.head = null; // while (this.head != null) { // ListNode curNext = head.next; // this.head.next = null; // this.head = curNext // } } }
无头单向非循环链表的整个过程的创建就是这样的,内容相对来说是比较多的,当然一次性理解肯定是非常难的,所以不需要太过焦虑,多画图,多练习肯定能有所提升,好了,此次的无头单向非循环链表就到这里,下一篇博客我们将介绍无头双向循环链表,如果有所收获,别忘了点赞收藏哦,有问题欢迎私信和评论,谢谢大家。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。