单链表3（数据结构）

冷不防 2023-10-09 13:42 45阅读 0赞

在[单链表1（数据结构）][1]中完成了对单链表的基本操作，[单链表2（数据结构）][2]中通过添加尾指针tail对单链表1进行了优化，可是我们有没有发现，无论是单链表1还是单链表2只能对结点数据域为整型的进行操作。如果要对结点数据域为其它数据类型的结点进行操作，要去改结点中value的数据类型，所以我们不如直接定义成泛型，又因为Node类只为SingleLink类使用，所以索性将Node类定义成SingleLink类的内部类（内部类在[Java内部类][Java]博客中有介绍）。  
废话不多说，直接上原码！！！

#### List接口 ####

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

#### SingleLink类 ####

public class SingleLink<E extends Comparable<E>> implements List<E> {
        //单向链表
        private Node<E> head;//用来标记链表的起始位置
        private Node<E> tail;// 标记链表的末尾位置
    
        //头部添加
        @Override
        public void addHead(E value) {
        
            //新结点的next = 原来头部位置
    //        Node newNode = new Node(value,null);
    //        newNode.setNext(head);
            Node<E> newNode = new Node<>(value, head);
            if(head == null){
         // 空链表，维护tail
                tail = newNode;
            }
            head = newNode;//更新新的头部结点位置
        }
    
        //尾部添加
        @Override
        public void addTail(E value) {
        
            Node<E> 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<E> p = head;
            while (p.getNext() != null) {
        
                p = p.getNext();
                if (p.getNext().getNext() == null) {
        
                    p.setNext(null);
                }
            }
            tail = p;
        }
    
        //删除特定结点
        @Override
        public void removeValue(E value) {
        
            //链表为空
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
            //考虑第一个结点是要删除的结点
            if (head.getValue().compareTo(value) == 0) {
        
                removeHead();
                return;
            }
    
            //只有一个结点
            if (head.getNext() == null && head.getValue().compareTo(value) != 0) {
        
                System.out.println("没有该结点");
                return;
            }
    
            //大于等于两个结点
            Node<E> p = head;
            while (p.getNext().getValue().compareTo(value) != 0) {
        
                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(E value) {
        
            if (head == null) {
        
                System.out.println("链表为空");
                return false;
            }
    
            for (Node<E> p = head; p != null; p = p.getNext()) {
        
                if (p.getValue().compareTo(value) == 0) {
        
                    return true;
                }
            }
            return false;
        }
    
        //打印
        public void show() {
        
            for (Node p = head; p != null; p = p.getNext()) {
        
                System.out.print(p.getValue() + " ");
            }
            System.out.println();
        }
    
        //内部类
        public static class Node<T> {
        
            private T value;
            private Node<T> next;
    
            public Node(T value, Node<T> next) {
        
                this.value = value;
                this.next = next; //下一个结点的地址
            }
    
            public T getValue() {
        
                return value;
            }
    
            public Node<T> getNext() {
        
                return next;
            }
    
            public void setValue(T value) {
        
                this.value = value;
            }
    
            public void setNext(Node<T> next) {
        
                this.next = next;
            }
        }
    
    }

#### TestDemo测试类 ####

public class TestDemo {
        
        public static void main(String[] args) {
        
            SingleLink<String> singleLink = new SingleLink<>();
            singleLink.addHead("abc");
            singleLink.addHead("hello");
            singleLink.addHead("world");
            singleLink.addHead("Java");
            singleLink.show();
            singleLink.addTail("HELLO");
            singleLink.show();
            singleLink.removeHead();
            singleLink.show();
            singleLink.removeTail();
            singleLink.show();
            singleLink.removeValue("hello");
            singleLink.show();
            if (singleLink.comtains("abc")){
        
                System.out.println("有该结点");
            }else {
        
                System.out.println("没有该结点");
            }
    
        }
    }

#### 运行结果演示 ####

演示操作value值为String类型，如TestDemo测试类。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]

[1]: https://blog.csdn.net/sheng0113/article/details/121562580?spm=1001.2014.3001.5501
[2]: https://blog.csdn.net/sheng0113/article/details/121582642?spm=1001.2014.3001.5501
[Java]: https://blog.csdn.net/sheng0113/article/details/121552011?spm=1001.2014.3001.5501
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/dd3c9a1be8444882b06bd61f2d5c07e4.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16