执行到这里,我们就有了这样一个节点,而链表就是由这一个个节点,串成的。
 
要想知道它怎么做,我们必须实现 它 的 一个 头插 和 尾插, 等等一系列操作,但是我们目前先不管它
我们现在最重要的是 了解 链表的结构
 
首先,我要区分清楚,链表 不是顺序表,不是一块连续的空间。 链表的每个元素 是由地址来连接起来的。
也就是说 我们不能使用普通思维模式 去思考 遍历链表的数据域的值
既然 链表是靠地址联系起来的,也就是说 靠 next域中 存储的地址来联系个节点的数据
这就是我们突破点。
利用 head 遍历每个每个节点的数据 写法 head = head/next,你可以参考上面的图,来细品。
这样我们就跳转到下一个节点,算了我还是画个图,请看下图(注意我埋了一个坑,你们等会就知道,只有被打过,才会知道疼)
遍历链表的时候, 尤其是我们现在所讲的 不带头的链表,一定注意,不要让 头引用丢失,创建一个替身变量,让它去做。
保证头引用指向的永远都是 头节点,
public boolean contains(int key){
ListNode cur = this.head;
while(cur!=null){
if(cur.val==key){
return true;
}
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;
}
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;
}
}
public void addIndex(int index,int data){
if(index<0 || index>size()){
System.out.println("插入数据节点的位置不合法");
return;
}
if(index==0){
addFirst(data);// 调用头插
return;
}
if(index== size()){
addLast(data);
return;
}
ListNode cur = findIndex(index);// 接收 index-1位置节点的地址
ListNode node = new ListNode(data);// 根据 data的值,新建一个节点
// 插入节点程序
node.next = 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;
}
public void remove(int key){
if(this.head == null){// head为空
System.out.println("链表为空,无数字可删除!");
return;
}
if(this.head.val == key){// 判断头节点是为删除数字
this.head = this.head.next;
return;
}
ListNode cur = searchPrev(key);// 找到删除节点的前一个节点
if(cur == null){
System.out.println("没有你要删除元素");
return;
}
ListNode del = cur.next;// 要删除的节点地址
cur.next = del.next;// 删除节点
}
// 寻找删除节点的前一个节点(key的前驱)
public ListNode searchPrev(int key){
ListNode cur = this.head;
while(cur.next != null){
if(cur.next.val == key)
{
return cur;
}
cur = cur.next;
}
return null;// 表示没找到
}
public ListNode removeAllKey(int key){
if(this.head == null){
return null; // 防止后面的cur出现空指针错误
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while(cur!=null){
if(cur.val == key){
prev.next = cur.next;
cur=cur.next;
}else{
prev = cur;
cur=cur.next;
}
}
// 最后处理头
if(this.head.val==key){
this.head = this.head.next;
}
return head;
}
public void clear(){
// this.head = null; 粗暴方法
// 温柔的(最稳的)
while(this.head!=null){
ListNode headNext = head.next;
this.head.next = null;
this.head = headNext;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/DarkAndGrey/article/details/121144745
内容来源于网络,如有侵权,请联系作者删除!