单链表基本操作(java)

小灰灰 2024-03-17 20:23 176阅读 0赞

#### 单链表 ####

*  一.自定义链表类
 *  二.自定义节点类
 *  三.链表中的基本方法
 *   *  1.头插法
     *  2.尾插法
     *  3.在任意位置插入
     *  4.删除第一次的关键字为key的节点
     *  5.删除所有关键字为key的元素
     *  6.是否包含关键字key
     *  7.获取链表长度
     *  8.遍历节点并输出
     *  9.清空链表

![在这里插入图片描述][46dc594b744c4b1c95d93aac5967fcdf.png_pic_center]

## 一.自定义链表类 ##

public class MySingleList {
        
    
         Node head; //头节点,Node类型
         int size;//链表中实际元素个数
         
         public void addFirst(int data) //头插法
         public void addLast(int data) //尾插法
         public void addIndex(int index,int data) //任意位置插入
         public boolean contains(int key) //是否包含关键字key
         public int getSize() //获取链表长度
         public void remove(int data) //删除第一次的关键字为key的节点
         public void removeAllKey(int key) //删除所有关键字为key的元素
         public void display() //遍历节点并输出
         
    }

## 二.自定义节点类 ##

class Node{
        
            public int value;//存储链表的值
            public Node next;//存储下一个链表的地址
            public Node(int value)
            {
        
                this.value = value;
            }
    
            public Node() {
        
            
            }
       }

节点类是链表类的内部类

## 三.链表中的基本方法 ##

### 1.头插法 ###

public void addFirst(int val)
        {
        
            Node node = new Node(val);
            node.next = head;
            head = node;
            size++;
        }

### 2.尾插法 ###

public void addLast(int data)
        {
        
            Node node = new Node(data);
            //如果一个节点都没有
            if(head==null){
        
                head = node;
                size++;
                return;
            }
            Node cur = head;
            //遍历到最后一个节点
            while(cur.next!=null)
            {
        
                cur = cur.next;
            }
            //插入
            cur.next = node;
            size++;
        }

### 3.在任意位置插入 ###

public void addIndex(int index,int data)
        {
        
            //下标不合法
            if(index<0||index>size)
            {
        
                throw new IllegalArgumentException("Index is invalid");
            }
            //在第一个位置插(头插)
            if(index==0)
            {
        
                addFirst(data);
                size++;
                return;
            }
            //在最后一个位置插
            if(index==size)
            {
        
                addLast(data);
                size++;
                return;
            }
            //一般情况
            Node node = new Node(data);
            Node cur = head;
            int count = 0;
            //循环找到插入位置的前一个位置
            while(count!=index-1)
            {
        
                cur = cur.next;
                count++;
            }
            node.next = cur.next;
            cur.next=node;
            size++;
        }

### 4.删除第一次的关键字为key的节点 ###

public void remove(int key) {
        
            //链表中一个元素都没有
            if(head==null)
            {
        
                return;
            }
            //第一个元素就是要删除的元素
            if(head.value==key)
            {
        
                head = head.next;
                size--;
                return;
            }
            //一般情况,遍历到要删除的前一个位置
            Node cur = head;
            while(cur.next!=null)
            {
        
                if(cur.next.value==key)
                {
        
                    cur.next = cur.next.next;
                    size--;
                    return;
                }
                //如果下一个不是要删的cur后移
                cur = cur.next;
            }
        }

### 5.删除所有关键字为key的元素 ###

public void removeAllKey(int key)
        {
        
            //链表中一个节点都不存在
            if(head==null)
            {
        
                return;
            }
            //双指针
            Node cur = head.next;
            Node prev = head;
            while(cur!=null)
            {
        
                if(cur.value==key)
                {
        
                    prev.next = cur.next;
                    size--;
                }else{
        
                    prev = cur;
                }
                cur =cur.next;
            }
            //处理第一个节点
            if(head.value==key)
            {
        
                head = head.next;
                size--;
            }
        }

### 6.是否包含关键字key ###

public boolean contains(int key)
        {
        
            Node cur = head;
            while(cur!=null)
            {
        
                if(cur.value==key)
                {
        
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }

### 7.获取链表长度 ###

public int getSize()
    {
        
       return  size;
    }

### 8.遍历节点并输出 ###

public void display()
    {
        
        Node cur = head;
        while(cur!=null)
         {
        
            System.out.print(cur.value+" ");
            cur = cur.next;
         }
    }

### 9.清空链表 ###

public void clear()
    {
        
      head = null;
    }

[46dc594b744c4b1c95d93aac5967fcdf.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/303bb82d23074006813cb09dc6de5e9b.png