投稿
  1. 极客之音首页
  2. 技术随笔

单链表1（数据结构）

小半 • • 技术随笔 • 阅读 183

导读：本篇文章讲解 单链表1（数据结构），希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

文章目录

单链表

1.链表的定义

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

相关术语：

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

在这里插入图片描述

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

如下：
在这里插入图片描述

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）考虑到链表为空的情况，同样适用。
在这里插入图片描述
代码如下：

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

2.4链表尾部添加操作

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

 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）链表不为空，只需要将头指针指向下一个结点。
在这里插入图片描述
代码如下：

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

2.6链表尾部删除操作

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

在这里插入图片描述

    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域置为下一个结点的下一个结点。
在这里插入图片描述

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.运行结果演示

在这里插入图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/95558.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！