欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

史上“最强”单链表实现(插入,删除,查找,求长...你想要的这里都有!)

程序员文章站 2022-04-21 10:58:10
文章目录序头插法尾插任意位置插入删除第一次出现的关键字删除所有指定关键字得到单链表的长度打印单链表清空单链表写在结尾序链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。这里说的单链表是指无头单向非循环链表。链表当然是由结点串起来的,那么,在写单链表实现前,我们需要定义一个结点的类。代码敲起来:class Node{ public int data;//定义当前结点的数据 public Node next;//下一个结点的引用 publ...

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。这里说的单链表是指无头单向非循环链表。
链表当然是由结点串起来的,那么,在写单链表实现前,我们需要定义一个结点的类。
代码敲起来:

class Node{
   public int data;//定义当前结点的数据
   public Node next;//下一个结点的引用

   public Node(int data){//构造方法
      this.data=data;
   }
}

头插法

 public void addFirst(int data){
    Node node=new Node(data);
    node.next=head;//新的结点指向头结点
    head=node;//新的结点变为第一个
}

尾插

public void addLast(int data) {
    Node node = new Node(data);
    if (this.head == null) {//判断是否为空链表
        this.head = node;
    } else {
        Node cur = this.head;
        while (cur.next != null) {//找到最后一个结点
            cur = cur.next;
        }
        cur.next = node;//最后一个结点指向新结点
    }
}

任意位置插入

public void addIndex(int index, int data) {
    if (index < 0 || index > getLength()) {//getlength是求链表长度见下;
        System.out.println("不合法");//判断任意位置是否合法
        return;
    }
    if (index == 0) {//第一个位置插入同头插法,可无
        addFirst(data);
    }
    if (index == this.getLength()) {//最后一个同尾插法,可无
        addLast(data);
    }
    Node node = new Node(data);
    Node cur = this.head;
    int count = 0;
    while (count < index - 1) {//找到插入的前一个位置
       cur = cur.next;
       count++;
    }
    node.next = cur.next;
    cur.next = node;
}

删除第一次出现的关键字

public void remove(int key) {
    if (this.head == null) {//链表为空
        return;
    }
    if (this.head.data == key) {//第一个结点为关键字
        this.head = this.head.next;
        return;
    }
    Node cur = this.head;
    while (cur.next != null) {
        if (cur.next.data == key) {//查找到关键字结点
           return cur;
        }
         cur = cur.next;
    }
    if (cur == null) {//找不到
    System.out.println("没有你要删除的数字");
    return;
    }
    Node del = cur.next;//删除
    cur.next = del.next;
 }

删除所有指定关键字

public void removeAllKey(int key) {
    if(this.head==null)return;//链表为空
    Node prev=this.head;//当前结点的前一个结点
    Node cur=this.head.next;//当前结点
    while(cur!=null){//判断cur是否为关键字
        if(cur.data==key){//是关键字
            prev.next=cur.next;//删除
            cur=cur.next;
        }else{//不是,接着往下
            prev=prev.next;
            cur=cur.next;
        }
    }
    if(this.head.data==key){//判断第一个结点是否为关键字
        this.head=this.head.next;
    }
}

得到单链表的长度

public int getLength() {
    int count = 0;//计数
    Node cur = this.head;
    while (cur != null) {
        count++;//遍历
        cur = cur.next;
    }
    return count;
}

打印单链表

public void display() {
    Node node = this.head;
    while (node != null) {
        System.out.print(node.data + " ");//打印
        node = node.next;//遍历
    }
    System.out.println();
}

清空单链表

public void clear(){
    this.head=null;//头结点为空 无法被引用
}

写在结尾

怎么样怎么样!是不是“最强”!(不许说不)码字不易,看到这就给点个赞啦,谢谢!您的每一份鼓励都是小编的动力哇!

本文地址:https://blog.csdn.net/xxxxd_/article/details/107667903

相关标签: Java