题外话
我很想发点nb的知识,但是路得一步一步走,饭也得一点一点吃,所以说
不积跬步无以至千里,不积小流无以成江海!!!
大家一起努力,未来属于我们!!
正题
理解链表
相信大家看到这都应该明白链表,那就简单讲下链表组成
今天实现LinkedList底层,LinkedList是一个双向链表,但是咱们这里其实是带头结点的单向链表,带头结点的单向链表中有三个很关键的变量,val和next,还有head
val是当前记录节点值的,而next是记录下一个节点的地址,将每一个节点通过逻辑连续联系在一起,这里可以理解为手拉手,但凡有一个人(节点)没有和后一个人拉手,就会导致无法找到后一个人
这里我们用的是静态内部类去表示节点,每一个节点都是LinkNode类型,所以存储地址的时候,next也应该是LinkNode类型,而头结点head是整个链表里的唯一关联链表元素,并非普通节点,就相当于我们需要通过一个首领去找到这个队伍的每个人,head就担当这样的首领
如果对链表不是很清晰可以看看下图,我用枚举法简单构造了一个带头节点的单向链表
代码实现
public class LinkedListBottom {
//定义一个静态内部类,表示节点,静态内部类对象不需要通过外部类的引用而获得
static class ListNode
{
int val;
public ListNode next;
public ListNode(int val) {
this.val=val;
}
}
//头结点不在节点里面,而是在链表里面,所以不定义在静态内部类里
public ListNode head;
//遍历链表
public void display() {
//不能改变head的职位,所以将head赋值给cur
ListNode cur=this.head;
//当cur不为空的时候打印cur的值,并继续指向下一节点
while (cur!=null)
{
System.out.print(cur.val+" ");
cur=cur.next;
}
}
//头插法
public void addFirst(int data){
//创建一个节点cur,并利用构造函数让val=data
ListNode node=new ListNode(data);
//如果头结点为空,直接放入头结点,否则把cur放入头结点之前,在让头结点指向cur
if (head==null)
{
this.head=node;
}
else {
node.next = this.head;
this.head = node;
}
}
//尾插法
public void addLast(int data){
//创建当前插入对象
ListNode node=new ListNode(data);
//不改变头结点位置,创建cur,让head赋值cur
ListNode cur=head;
//如果链表没有元素则直接插入元素node,否则先找到最后一个元素,在后面插入node
if(head==null)
{
this.head=node;
}
else {
while (cur.next!=null)
{
cur=cur.next;
}
cur.next=node;
}
}
//任意位置插入
public void addIndex(int index,int data){
//先给出cur,让head赋值给cur,确保head位置不变
ListNode cur=this.head;
//创建node对象,将data赋值
ListNode node=new ListNode(data);
//如果插入位置比0小,插入位置比整个元素数量都长,就直接返回
if (index<0||index>size())
{
return;
}
//如果插入位置为0,也就相当于头插法
if (index==0)
{
addFirst(data);
}
//如果插入位置在末尾,也就相当于尾插法
if(index==size())
{
addLast(data);
return;
}
//假设插入第三个位置,只需要找到第二个位置的元素
while (index-1!=0)
{
index--;
cur=cur.next;
}
//index-1=0,就说明已经到了插入位置的前一个位置,
node.next= cur.next;
cur.next=node;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur=this.head;
while(cur!=null)
{
if (cur.val==key)
{
return true;
}
cur=cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
//分析可能出现的情况:
//1.链表为空
//2.头结点位置找到key
//3.除了头结点的位置找到key
//4.找不到要删除的元素
//先把head赋值cur
ListNode cur=this.head;
//链表为空
if (cur==null)
{
System.out.println("链表为空!!");
return;
}
if (head.val==key)
{
head=head.next;
System.out.println("删除成功!!");
return;
}
while(cur.next!=null) {
if (cur.next.val == key) {
cur.next = cur.next.next;
System.out.println("删除成功!!");
return;
} else {
cur = cur.next;
}
}
System.out.println("链表没有要删除的元素!!");
}
//删除所有值为key的节点
public void removeAllKey(int key){
//链表为空的情况!
if (head==null)
{
System.out.println("链表为空!!");
return;
}
//将head给到pre,让pre成为cur的前驱,而cur是pre后继
ListNode pre=head;
ListNode cur=pre.next;
//cur不为空时,判断除头结点以外的元素val是否等于key
while (cur!=null)
{
//如果cur.val==key的话,就让pre的next指向cur的下一个节点,让cur指向下一个节点,完成删除
if (cur.val==key)
{
pre.next=cur.next;
cur=cur.next;
}
else {
pre=cur;
cur = cur.next;
}
}
//最后再看头结点val是不是等于key,然后删除头结点就可以了
if (head.val==key)
{
head=head.next;
}
System.out.println("已删除完成!!");
}
//得到单链表的长度
public int size(){
ListNode cur=this.head;
int count=0;
while(cur!=null)
{
count++;
cur=cur.next;
}
return count;
}
public void clear(){
//最简单粗暴方法头结点为空!!
//但是这里咱们细节一点点,让每一个节点都为空!
//先让head赋值cur
ListNode cur=head;
//cur不为空的全部为空
while(cur!=null)
{
//提前让curNext为cur的下一个节点
ListNode curNext=cur.next;
//然后让cur的next为null
cur.next=null;
//因为已经先记录了curNext,所以直接赋给cur就可以了
cur=curNext;
}
//最后让头结点为null
head=null;
}
}
小结
今天内容就这么多,希望大家多多支持!!!
标签：head,ListNode,cur,next,链表,key,底层,数据结构,LinkedList From： https://blog.csdn.net/weixin_67836079/article/details/136783336