单链表2（数据结构）

￡神魔★判官ぃ 2023-10-09 13:41 105阅读 0赞

#### 文章目录 ####

*  1.链表操作
 *   *  1.1链表头部添加操作
     *  1.2链表尾部添加操作
     *  1.3链表头部删除操作
     *  1.4链表尾部删除操作
     *  1.5删除特定结点操作
     *  1.6查找特定结点操作
     *  1.7打印链表结点value值操作
 *  2.源码
 *   *  List接口：
     *  Node类
     *  SingleLink类
     *  TestDemo测试类
 *  4.运行结果演示

在 [单链表1（数据结构）][1]博客中我们完成了对单链表的基本操作，链表头部添加操作，链表尾部添加操作，链表头部删除操作，链表尾部删除操作，删除特定结点操作，查找特定结点操作。我们是通过定义一个头指针进行操作的，在今天的单链表2中，再定义一个尾指针完成对单链表的基本操作。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]

## 1.链表操作 ##

### 1.1链表头部添加操作 ###

1）如果链表为空，头指针和尾指针都需要维护，指向新结点。  
2）链表不为空，新结点next域指向原来头结点地址，更新头指针，指向新结点。  
![在这里插入图片描述][698b8580225248a0bef10d3b8ab23bd0.gif]

public void addHead(int value) {
        
            //新结点的next = 原来头部位置
    //        Node newNode = new Node(value,null);
    //        newNode.setNext(head);
            Node newNode = new Node(value, head);
            if(head == null){
         // 空链表，维护tail
                tail = newNode;
            }
            head = newNode;//更新新的头部结点位置
        }

### 1.2链表尾部添加操作 ###

1）链表为空，头指针指向新结点，尾指针指向新结点。  
2）链表不为空，头指针不用变，原先尾结点next域指向新结点的位置，最后维护维护尾指针指向新结点。  
![在这里插入图片描述][c507b8b7be79427d86c143fe9c89e7eb.gif]

public void addTail(int value) {
        
            Node newNode = new Node(value, null);
            if (head == null) {
        
                head = newNode;
            }else {
        
                tail.setNext(newNode);
            }
    
            tail = newNode;
        }

### 1.3链表头部删除操作 ###

1）链表为空，不需要操作，直接返回，头指针和尾指针也不需要维护。  
2）链表长度为1，尾指针置为null，头指针置为null，即head = head.getNext();  
3）链表长度大于等于1，尾指针不用维护，头指针指向下一个结点的地址。  
![在这里插入图片描述][c9484e169b124e37ac70f86d178ac7a9.gif]

public void removeHead() {
        
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
            //结点 == 1
            if (head.getNext() == null) {
        
                tail = null;
            }
    
            //结点>=2
            head = head.getNext();
        }

### 1.4链表尾部删除操作 ###

1）链表长度为空，不操作，头指针和尾指针都不要维护。  
2）链表只有一个结点，头指针置为null，尾指针置为null。  
3）链表大于等于两个结点，遍历链表，如果当前结点的下一个结点的next域为null，将本结点的next域置为null，然后维护尾结点。  
![在这里插入图片描述][fd7f71773b844de5ae37bf39de771fb3.gif]

public void removeTail() {
        
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
    
    
            //只有一个结点
            if (head.getNext() == null) {
        
                head = null;
                tail = null;
                return;
            }
    
            //大于等于两个结点
            Node p = head;
            while (p.getNext() != null) {
        
                p = p.getNext();
                if (p.getNext().getNext() == null) {
        
                    p.setNext(null);
                }
            }
            tail = p;
        }

### 1.5删除特定结点操作 ###

1）链表为空，不操作。  
2）链表第一个结点为待删结点，调用头部删除操作removeTail()。  
3）只有一个结点，且不是待删结点，不操作。  
4）大于等于两个结点，遍历链表，当当前结点的下一个结点的value值是要删除的结点，把当前结点next域指向下下个结点。如果最后一个结点是要待删除的结点，那么把当前结点的next域置为null，调整尾指针。  
![在这里插入图片描述][871c9903cac6442b97164defad6afe90.gif]

public void removeValue(int value) {
        
            //链表为空
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
            //考虑第一个结点是要删除的结点
            if (head.getValue() == value) {
        
                removeHead();
                return;
            }
    
            //只有一个结点
            if (head.getNext() == null && head.getValue() != value) {
        
                System.out.println("没有该结点");
                return;
            }
    
            //大于等于两个结点
            Node p = head;
            while (p.getNext().getValue() != value) {
        
                p = p.getNext();
            }
            if (p.getNext() == null) {
        
                System.out.println("没有该结点");
            }
    		//如果最后一个结点为待删结点
            if (p.getNext() == tail) {
        
                tail = p;
            }
    
            p.setNext(p.getNext().getNext());
        }

### 1.6查找特定结点操作 ###

public boolean comtains(int value) {
        
            if (head == null) {
        
                System.out.println("链表为空");
                return false;
            }
    
            for (Node p = head; p != null; p = p.getNext()) {
        
                if (p.getValue() == value) {
        
                    return true;
                }
            }
            return false;
        }

### 1.7打印链表结点value值操作 ###

public void show() {
        
            for (Node p = head; p != null; p = p.getNext()) {
        
                System.out.print(p.getValue() + " ");
            }
            System.out.println();
        }

## 2.源码 ##

### List接口： ###

public interface List {
        
        void addHead(int value);
        void addTail(int value);
        void removeHead();
        void removeTail();
        void removeValue(int value);
        boolean comtains(int value);
    }

### Node类 ###

public class Node {
        
        private int value;
        private Node next;
    
        public Node(int value, Node next) {
        
            this.value = value;
            this.next = next; //下一个结点的地址
        }
    
        public int getValue() {
        
            return value;
        }
    
        public Node getNext() {
        
            return next;
        }
    
        public void setValue(int value) {
        
            this.value = value;
        }
    
        public void setNext(Node next) {
        
            this.next = next;
        }
    }

### SingleLink类 ###

public class SingleLink implements List {
        //单向链表
        private Node head;//用来标记链表的起始位置
        private Node tail;// 标记链表的末尾位置
    
        //头部添加
        @Override
        public void addHead(int value) {
        
            //新结点的next = 原来头部位置
    //        Node newNode = new Node(value,null);
    //        newNode.setNext(head);
            Node newNode = new Node(value, head);
            if(head == null){
         // 空链表，维护tail
                tail = newNode;
            }
            head = newNode;//更新新的头部结点位置
        }
    
        //尾部添加
        @Override
        public void addTail(int value) {
        
            Node newNode = new Node(value, null);
            if (head == null) {
        
                head = newNode;
            }else {
        
                tail.setNext(newNode);
            }
    
            tail = newNode;
        }
    
        //删除头部
        @Override
        public void removeHead() {
        
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
            //结点 == 1
            if (head.getNext() == null) {
        
                tail = null;
            }
    
            //结点>=2
            head = head.getNext();
        }
    
        //删除尾部
        @Override
        public void removeTail() {
        
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
    
    
            //只有一个结点
            if (head.getNext() == null) {
        
                head = null;
                tail = null;
                return;
            }
    
            //大于等于两个结点
            Node p = head;
            while (p.getNext() != null) {
        
                p = p.getNext();
                if (p.getNext().getNext() == null) {
        
                    p.setNext(null);
                }
            }
            tail = p;
        }
    
        //删除特定结点
        @Override
        public void removeValue(int value) {
        
            //链表为空
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
            //考虑第一个结点是要删除的结点
            if (head.getValue() == value) {
        
                removeHead();
                return;
            }
    
            //只有一个结点
            if (head.getNext() == null && head.getValue() != value) {
        
                System.out.println("没有该结点");
                return;
            }
    
            //大于等于两个结点
            Node p = head;
            while (p.getNext().getValue() != value) {
        
                p = p.getNext();
            }
            if (p.getNext() == null) {
        
                System.out.println("没有该结点");
            }
    		//如果最后一个结点为待删结点
            if (p.getNext() == tail) {
        
                tail = p;
            }
    
            p.setNext(p.getNext().getNext());
        }
    
        //查找特定结点
        @Override
        public boolean comtains(int value) {
        
            if (head == null) {
        
                System.out.println("链表为空");
                return false;
            }
    
            for (Node p = head; p != null; p = p.getNext()) {
        
                if (p.getValue() == value) {
        
                    return true;
                }
            }
            return false;
        }
    
        //打印
        public void show() {
        
            for (Node p = head; p != null; p = p.getNext()) {
        
                System.out.print(p.getValue() + " ");
            }
            System.out.println();
        }
    }

### TestDemo测试类 ###

public class TestDemo {
        
        public static void main(String[] args) {
        
            SingleLink singleLink = new SingleLink();
            singleLink.addHead(5);
            singleLink.addHead(4);
            singleLink.addHead(3);
            singleLink.addHead(2);
            singleLink.addHead(1);
            singleLink.show();
            singleLink.addTail(6);
            singleLink.show();
            singleLink.removeHead();
            singleLink.show();
            singleLink.removeTail();
            singleLink.show();
            singleLink.removeValue(3);
            singleLink.show();
            if (singleLink.comtains(5)) {
        
                System.out.println("有该结点");
            }else {
        
                System.out.println("没有该结点");
            }
    
        }
    }

## 4.运行结果演示 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[1]: https://blog.csdn.net/sheng0113/article/details/121562580
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/5c7a68db2777403e87819f9fe7d46c3d.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[698b8580225248a0bef10d3b8ab23bd0.gif]: https://img-blog.csdnimg.cn/698b8580225248a0bef10d3b8ab23bd0.gif
[c507b8b7be79427d86c143fe9c89e7eb.gif]: https://img-blog.csdnimg.cn/c507b8b7be79427d86c143fe9c89e7eb.gif
[c9484e169b124e37ac70f86d178ac7a9.gif]: https://img-blog.csdnimg.cn/c9484e169b124e37ac70f86d178ac7a9.gif
[fd7f71773b844de5ae37bf39de771fb3.gif]: https://img-blog.csdnimg.cn/fd7f71773b844de5ae37bf39de771fb3.gif
[871c9903cac6442b97164defad6afe90.gif]: https://img-blog.csdnimg.cn/871c9903cac6442b97164defad6afe90.gif
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/5092a08dfbc8402e9443852fbc1d100b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16