Sequential And Linked Lists - 顺序表 和 链表 - 单向链表部分 - java(图文并茂,你值得一看)

x33g5p2x  于2021-11-22 转载在 Java  
字(3.0k)|赞(0)|评价(0)|浏览(176)

回顾 和 链表

接下来我们来通过代码 来认识链表

1 准备工作

2 根据 前面 所说的,根据节点的特性写一个类

3. new 节点

执行到这里,我们就有了这样一个节点,而链表就是由这一个个节点,串成的。

 

我们已经知道怎么实例化一个节点,但是我们又怎么做,才能知道下一个节点的地址呢?

要想知道它怎么做,我们必须实现 它 的 一个 头插 和 尾插, 等等一系列操作,但是我们目前先不管它
      我们现在最重要的是 了解 链表的结构

我先来把前面的东西讲清楚。

链表的头引用 head

理解链表中: 带头、不带头、单向、双向、循环、不循环的意思。

带头 和 不带头

循环 和 不循环

单向 和 双向

至此 我们将链表的结构 全部分析完了。

接下来,我会以代码的形式 来带你们认识 链表。

以穷举的方式 创建一个链表 (这方法很low,不建议去这样写,现在只是为了帮助我们去理解链表)

现在 我要实现 单向 不带头 非循环的链表

回到代码

 

创建一个函数,来实现链表的结构

先创建五个节点

将五个节点连接起来。

现在链表结构,已经构造好了,它的头节点就是节点1,将 节点一 的地址 赋给 头引用 head

遍历链表数据

首先,我要区分清楚,链表 不是顺序表,不是一块连续的空间。 链表的每个元素 是由地址来连接起来的。
   也就是说 我们不能使用普通思维模式 去思考 遍历链表的数据域的值

 既然 链表是靠地址联系起来的,也就是说 靠 next域中 存储的地址来联系个节点的数据
 这就是我们突破点。
  利用 head 遍历每个每个节点的数据  写法 head =  head/next,你可以参考上面的图,来细品。
  这样我们就跳转到下一个节点,算了我还是画个图,请看下图(注意我埋了一个坑,你们等会就知道,只有被打过,才会知道疼)

揭秘坑

解决方法 (创建一个head的替身 【cur == current — 目前的】,来代替head去遍历链表数据)

代码如下:

调用者程序

效果图

另外注意一点

效果图

总结:

遍历链表的时候, 尤其是我们现在所讲的 不带头的链表,一定注意,不要让 头引用丢失,创建一个替身变量,让它去做。
 保证头引用指向的永远都是 头节点,

链表要实现的功能

查找关键字key是否在链表当中

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;
}

附图

效果图

删除第一次出现关键字为key的节点

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;// 表示没找到
}

附图

效果图

删除所有值为key的节点

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;
    }
}

附图

效果图

还有一种更直观的方法,请看连续图

附上链表程序

调用者程序

本文至此,就将链表的所有功能都实现了。有疑问的可以在下方评论,大家一起共同进步

相关文章

微信公众号

最新文章

更多

目录