单链表1（数据结构）

喜欢ヅ旅行 2023-10-09 13:41 36阅读 0赞

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

*  单链表
 *   *  1.链表的定义
     *  2.链表操作
     *   *  2.1定义一个结点
         *  2.2 定义一个链表
         *  2.3 链表头部添加操作
         *  2.4链表尾部添加操作
         *  2.5链表头部删除操作
         *  2.6链表尾部删除操作
         *  2.7删除特定结点操作
         *  2.8查找特定结点操作
         *  2.9打印链表结点value值操作
     *  3.源码
     *   *  List接口
         *  Node类
         *  SingleLink类
         *  TestDemo测试类
     *  4.运行结果演示

## 单链表 ##

### 1.链表的定义 ###

**线性表的链式存储结构**：线性表中数据元素（结点）在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理位置上不一定相邻。

**相关术语：**

> 结点:数据元素的存储映像。由数据域和指针域两部分组成。  
> 数据域：存储数据元素信息的域称为数据域。  
> 指针域：存储直接后继存储位置的域称为指针域。

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

> 头结点：链表的第一个结点。  
> 尾结点：链表的最后一个结点，尾结点的指针域为空。  
> 头指针：指向头结点的指针，保存头结点的地址。

如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]

### 2.链表操作 ###

#### 2.1定义一个结点 ####

因为节点有两部分构成，数据域和指针域 。所以定义一个Node类，包含两部分实例变量，value代表数据域，next代表指针域。  
**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;
        }
    }

#### 2.2 定义一个链表 ####

因为需要一个头指针用来标记链表的起始位置，在SingleLink类中添加一个实例变量head；  
**singleLink类：**

public class SingleLink {
        
           private Node head;//用来标记链表的起始位置
    }

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

头部添加操作addHead  
1）需要创建一个新的结点，新结点的next域指向原先第一个结点的位置。  
2）头指针要指向新结点。  
3）考虑到链表为空的情况，同样适用。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**代码如下：**

public void addHead(int value) {
        
            //新结点的next = 原来头部位置
           Node newNode = new Node(value,null);
           newNode.setNext(head);
           
           head = newnNode;//更新新的头部结点位置
        }

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

尾部添加操作addTail  
1） 如果链表为空，头指针直接指向新结点。  
2）链表不为空，遍历链表（创建一个结点p 遍历链表），找到尾结点，使尾结点的next域指向即将插入的新结点。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**代码如下：**

public void addTail(int value) {
        
            Node newNode = new Node(value, null);
            //链表为空
            if (head == null) {
        
                head = newNode;
                return;
            }
    		//链表不为空，遍历链表，找到尾结点
            Node p = head;
            while (p.getNext() != null) {
        
                p = p.getNext();
            }
    
            p.setNext(newNode);
        }

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

链表头部删除操作removeHead  
1）如果链表为空，直接返回，不操作  
2）链表不为空，只需要将头指针指向下一个结点。  
![在这里插入图片描述][13abe11e27e746bbbeb6e621aa81c874.gif]  
**代码如下：**

public void removeHead() {
        
       		//链表为空
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
            //链表不为空
            head = head.getNext();
        }

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

链表尾部删除操作removeTail  
1）如果链表为空，不操作，直接返回。  
2）链表只有一个结点，直接把head置为null。  
3）链表有多个结点，遍历该链表，如果当前节点的下一个结点为空（即为尾结点），把当前结点的next域置为null，删除尾结点成功。

![在这里插入图片描述][fb2687b8238043599c6fac01fcf89ffd.gif]

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

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

删除特定结点操作removeValue  
1）链表为空，直接返回。  
2）如果第一个结点就是要待删除的结点，调用头部删除方法removeHead。  
3）如果只有一个结点，并且不是要待删除的结点，表示链表中没有该结点，返回。  
4）链表中有大于等于两个结点数，遍历链表，如果当前结点的下一个结点value值是要删除的结点，那么把当前结点的next域置为下一个结点的下一个结点。  
![在这里插入图片描述][567c7f03de6447ed9f50977a14f05b36.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("没有该结点");
            } else {
        
                p.setNext(p.getNext().getNext());
            }
        }

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

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

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

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

### 3.源码 ###

#### 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;//用来标记链表的起始位置
    
    
        //头部添加
        @Override
        public void addHead(int value) {
        
            //新结点的next = 原来头部位置
    //        Node newnode = new Node(value,null);
    //        newnode.setNext(head);
            Node newnNode = new Node(value, head);
    
            head = newnNode;//更新新的头部结点位置
        }
    
        //尾部添加
        @Override
        public void addTail(int value) {
        
            Node newNode = new Node(value, null);
            if (head == null) {
        
                head = newNode;
                return;
            }
    
            Node p = head;
            while (p.getNext() != null) {
        
                p = p.getNext();
            }
    
            p.setNext(newNode);
        }
    
        //删除头部
        @Override
        public void removeHead() {
        
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
            //>=1
            head = head.getNext();
        }
    
        //删除尾部
        @Override
        public void removeTail() {
        
            if (head == null) {
        
                System.out.println("链表为空");
                return;
            }
    
    
            //只有一个结点
            if (head.getNext() == null) {
        
                head = null;
                return;
            }
    
            //大于等于两个结点
            Node p = head;
            while (p.getNext() != null) {
        
                p = p.getNext();
                if (p.getNext().getNext() == null) {
        
                    p.setNext(null);
                }
            }
        }
    
        //删除特定结点
        @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("没有该结点");
            } else {
        
                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 3]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_19_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/07d9ec24824b4edb82f55f7cc071f31a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_19,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/39214366db744499b02d1ed52f1aa531.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/555a0c5440d341038ac7144ca7c04d47.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/79fd2cc6ebe74ca5a32fa2678406e99c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[13abe11e27e746bbbeb6e621aa81c874.gif]: https://img-blog.csdnimg.cn/13abe11e27e746bbbeb6e621aa81c874.gif
[fb2687b8238043599c6fac01fcf89ffd.gif]: https://img-blog.csdnimg.cn/fb2687b8238043599c6fac01fcf89ffd.gif
[567c7f03de6447ed9f50977a14f05b36.gif]: https://img-blog.csdnimg.cn/567c7f03de6447ed9f50977a14f05b36.gif
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/58fe89e5c3f24484b876a38dd1ace1ca.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16