数据结构——单链表的代码实现（Java）

雨点打透心脏的1/2处 2023-10-08 13:17 77阅读 0赞

上接  
[数据结构——线性表][Link 1].  
这篇文章  
**1、结点类:**  
单链表是由一个一个结点组成的，因此，要设计单链表类，必须先设计结点类。结点类的成员变量有两个:一个是数据元素，另一个是表示下一个结点的对象引用(即指针)。  
步骤如下:  
(1)头结点的构造（设置指针域即可)  
(2)非头结点的构造  
(3)获得当前结点的指针域  
(4)获得当前结点数据域的值  
(5)设置当前结点的指针域  
(6)设置当前结点数据域的值  
注:类似于get和set方法，成员变量是数据域和指针域。  
代码实现:  
(1)List.java:(链表本身也是线性表，只不过物理存储上不连续)

//线性表接口
    public interface List {
        
        //获得线性表长度
        public int size();
    
        //判断线性表是否为空
        public boolean isEmpty();
    
        //插入元素
        public void insert(int index, Object obj) throws Exception;
    
        //删除元素
        public void delete(int index) throws Exception;
    
        //获取指定位置的元素
        public Object get(int index) throws Exception;
    }

(2)Node.java:结点类

//结点类
    public class Node {
        
    
        Object element; //数据域
        Node next;  //指针域
    
        //头结点的构造方法
        public Node(Node nextval) {
        
            this.next = nextval;
        }
    
        //非头结点的构造方法
        public Node(Object obj, Node nextval) {
        
            this.element = obj;
            this.next = nextval;
        }
    
        //获得当前结点的指针域
        public Node getNext() {
        
            return this.next;
        }
    
        //获得当前结点数据域的值
        public Object getElement() {
        
            return this.element;
        }
        //设置当前结点的指针域
        public void setNext(Node nextval) {
        
            this.next = nextval;
        }
    
        //设置当前结点数据域的值
        public void setElement(Object obj) {
        
            this.element = obj;
        }
    
        public String toString() {
        
            return this.element.toString();
        }
    }

**2、单链表类：**  
单链表类的成员变量至少要有两个:一个是头指针，另一个是单链表中的数据元素个数。但是，如果再增加一个表示单链表当前结点位置的成员变量，则有些成员函数的设计将更加方便。  
代码实现:  
(3)LinkList.java:单向链表类(核心代码)

//单向链表类
    public class LinkList implements List {
        
    
        Node head; //头指针
        Node current;//当前结点对象
        int size;//结点个数
    
        //初始化一个空链表
        public LinkList()
        {
        
            //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
            this.head = current = new Node(null);
            this.size =0;//单向链表，初始长度为零。
        }
    
        //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。
        //比如我们要在a2这个节点之前进行插入操作，那就先要把当前节点对象定位到a1这个节点，然后修改a1节点的指针域
        public void index(int index) throws Exception
        {
        
            if(index <-1 || index > size -1)
            {
        
              throw new Exception("参数错误！");
            }
            //说明在头结点之后操作。
            if(index==-1)    //因为第一个数据元素结点的下标是0，那么头结点的下标自然就是-1了。
                return;
            current = head.next;
            int j=0;//循环变量
            while(current != null&&j<index)
            {
        
                current = current.next;
                j++;
            }
    
        }
    
        @Override
        public void delete(int index) throws Exception {
        
            // TODO Auto-generated method stub
            //判断链表是否为空
            if(isEmpty())
            {
        
                throw new Exception("链表为空，无法删除！");
            }
            if(index <0 ||index >size)
            {
        
                throw new Exception("参数错误！");
            }
            index(index-1);//定位到要操作结点的前一个结点对象。
            current.setNext(current.next.next);
            size--;
        }
    
        @Override
        public Object get(int index) throws Exception {
        
            // TODO Auto-generated method stub
            if(index <-1 || index >size-1)
            {
        
                throw new Exception("参数非法！");
            }
            index(index);
    
            return current.getElement();
        }
    
        @Override
        public void insert(int index, Object obj) throws Exception {
        
            // TODO Auto-generated method stub
            if(index <0 ||index >size)
            {
        
                throw new Exception("参数错误！");
            }
            index(index-1);//定位到要操作结点的前一个结点对象。
            current.setNext(new Node(obj,current.next));
            size++;
        }
    
        @Override
        public boolean isEmpty() {
        
            // TODO Auto-generated method stub
            return size==0;
        }
    
        @Override
        public int size() {
        
            // TODO Auto-generated method stub
            return this.size;
        }
    
    
    }

**3、测试类:(单链表的应用)**  
使用单链表建立一个线性表，依次输入十个0-99之间的随机数，删除第5个元素，打印输出该线性表。  
(4)Test.java:

public class Test {
        
    
        public static void main(String[] args) throws Exception {
        
            // TODO Auto-generated method stub
            LinkList list = new LinkList();
            for (int i = 0; i < 10; i++) {
        
                int temp = ((int) (Math.random() * 100)) % 100;
                list.insert(i, temp);
                System.out.print(temp + " ");
            }
    
            list.delete(4);
            System.out.println("\n------删除第五个元素之后-------");
            for (int i = 0; i < list.size; i++) {
        
                System.out.print(list.get(i) + " ");
            }
        }
    
    }

运行效果：  
![在这里插入图片描述][8de48176434243aea4dca153b0d91ca9.png]  
**4、开发可用的链表:**  
对于链表实现，Node类是整个操作的关键，但是首先来研究一下之前程序的问题: Node是一个单独的类，那么这样的类是可以被用户直接使用的，但是这个类由用户直接去使用，没有任何的意义，即: `Node这个类有用，但是不能让用户去用，只能让LinkList类去调用，内部类Node中完成`。  
于是，我们需要`把Node类定义为内部类，并且在Node类中去完成addNode和delNote等操作。使用内部类的最大好处是可以和外部类进行私有操作的互相访问`。  
注:内部类访问的特点是:内部类可以直接访问外部类的成员，包括私有;外部类要访问内部类的成员，必须先创建对象。  
**1、增加数据:**  
public Boolean add(数据对象)代码实现:  
(1) LinkList.java:(核心代码)

public class LinkList {
        
        private Node root; //定义一个根节点
    
        //方法：增加节点
        public boolean add(String data) {
        
    
            if (data == null) {
             // 如果添加的是一个空数据，那增加失败
                return false;
            }
    
            // 将数据封装为节点，目的：节点有next可以处理关系
            Node newNode = new Node(data);
            // 链表的关键就在于根节点
            if (root == null) {
          //如果根节点是空的，那么新添加的节点就是根节点。(第一次调用add方法时，根节点当然是空的了)
                root = newNode;
            } else {
        
                root.addNode(newNode);
    
            }
    
            return true;
    
        }
    
    
        //定义一个节点内部类（假设要保存的数据类型是字符串）
        //比较好的做法是，将Node定义为内部类，在这里面去完成增删、等功能，然后由LinkList去调用增、删的功能
        class Node {
        
            private String data;
            private Node next;  //next表示：下一个节点对象（单链表中）
    
            public Node(String data) {
        
                this.data = data;
            }
    
            public void addNode(Node newNode) {
        
    
                //下面这段用到了递归，需要反复理解
                if (this.next == null) {
           // 递归的出口：如果当前节点之后没有节点，说明我可以在这个节点后面添加新节点
                    this.next = newNode;   //添加新节点
                } else {
        
                    this.next.addNode(newNode);  //向下继续判断，直到当前节点之后没有节点为止
    
                }
            }
        }
    }

代码解释:  
14行:如果我们第一次调用add方法，那根结点肯定是空的，此时add的是根节点。  
当继续调用add方法时，此时是往根节点后面添加数据，需要用到递归(42行)，这个递归需要在内部类中去完成。递归这段代码需要去反复理解。  
（2）LinkListDemo.java:

public class LinkListDemo {
        
    
        public static void main(String[] args) {
        
            LinkList list = new LinkList();
            boolean flag = list.add("haha");
            System.out.println(flag);
        }
    
    }

![在这里插入图片描述][d0201102c34746f18620ba34ea10a3e6.png]  
**2、增加多个数据：**

*  public boolean addAll(数据 对象 \[\] )

上面的操作是每次增加了一个对象，那么如果现在要求增加多个对象呢，例如：增加对象数组。可以采用循环数组的方式，每次都调用add()方法。

在上面的（1）LinkList.java中加入如下代码：

//方法：增加一组数据
        public boolean addAll(String data[]) {
             // 一组数据
            for (int x = 0 ; x < data.length ; x ++) {
        
                if (!this.add(data[x])) {
         // 只要有一次添加不成功，那就是添加失败
                    return false ;
                }
            }
            return true ;
        }

**3、统计数据个数：**

*  public int size()

在一个链表之中，会保存多个数据（每一个数据都被封装为Node类对象），那么要想取得这些保存元素的个数，可以增加一个size()方法完成。

具体做法如下：

在上面的（1）LinkList.java中增加一个统计的属性count：

private int size ; // 统计个数

当用户每一次调用add()方法增加新数据的时候应该做出统计：（下方第18行代码）

//添加节点
        public boolean add(String data) {
        
    
            if (data == null) {
             // 如果添加的是一个空数据，那增加失败
                return false;
            }
    
            // 将数据封装为节点，目的：节点有next可以处理关系
            Node newNode = new Node(data);
            // 链表的关键就在于根节点
            if (root == null) {
          //如果根节点是空的，那么新添加的节点就是根节点。(第一次调用add方法时，根节点当然是空的了)
                root = newNode;
            } else {
        
                root.addNode(newNode);
    
            }
    
            this.size++;
            return true;
    
        }

而size()方法就是简单的将count这个变量的内容返回：

//获取数据的长度
        public int size() {
        
            return this.size;
        }

**4、判断是否是空链表：**

*  public boolean isEmpty()

所谓的空链表指的是链表之中不保存任何的数据，实际上这个null可以通过两种方式判断：一种判断链表的根节点是否为null，另外一个是判断保存元素的个数是否为0。

在LinkList.java中添加如下代码：

//判断是否为空链表
        public boolean isEmpty() {
        
            return this.size == 0;
        }

**5、查找数据是否存在：**

*  public boolean contains(数据 对象)

现在如果要想查询某个数据是否存在，那么基本的操作原理：逐个盘查，盘查的具体实现还是应该交给Node类去处理，但是在盘查之前必须有一个前提：有数据存在。

在LinkList.java中添加查询的操作：

//查询数据是否存在
        public boolean contains(String data) {
              // 查找数据
            // 根节点没有数据，查找的也没有数据
            if (this.root == null || data == null) {
        
                return false;        // 不需要进行查找了
            }
            return this.root.containsNode(data);        // 交给Node类处理
        }

紧接着，在Node类之中，完成具体的查询，查询的流程：  
　　判断当前节点的内容是否满足于查询内容，如果满足返回true；  
　　如果当前节点的内容不满足，则向后继续查，如果已经没有后续节点了，则返回false。

代码实现：

//判断节点是否存在
            public boolean containsNode(String data) {
              // 查找数据
                if (data.equals(this.data)) {
             // 与当前节点数据吻合
                    return true;
                } else {
               // 与当前节点数据不吻合
                    if (this.next != null) {
           // 还有下一个节点
                        return this.next.containsNode(data);
                    } else {
               // 没有后续节点
                        return false;        // 查找不到
                    }
                }
            }

**6、删除数据：**

*  public boolean remove(数据 对象)

在LinkList.java中加入如下代码：

//方法：删除数据
        public boolean remove(String data) {
         //要删除的节点，假设每个节点的data都不一样
    
            if (!this.contains(data)) {
         //要删除的数据不存在
                return false;
            }
    
            if (root != null) {
        
                if (root.data.equals(data)) {
          //说明根节点就是需要删除的节点
                    root = root.next;  //让根节点的下一个节点成为根节点，自然就把根节点顶掉了嘛（不像数组那样，要将后面的数据在内存中整体挪一位）
                } else {
          //否则
                    root.removeNode(data);
                }
            }
            size--;
            return true;
    
        }

注意第2代码中，我们是假设删除的这个String字符串是唯一的，不然就没法删除了。

删除时，我们需要从根节点开始判断，如果根节点是需要删除的节点，那就直接删除，此时下一个节点变成了根节点。

然后，在Node类中做节点的删除：

//删除节点
            public void removeNode(String data) {
        
                if (this.next != null) {
        
                    if (this.next.data.equals(data)) {
        
                        this.next = this.next.next;
                    } else {
        
                        this.next.removeNode(data);
                    }
                }
    
            }

**7、输出所有节点：**  
在LinkList.java中加入如下代码：

//输出所有节点
        public void print() {
        
            if (root != null) {
        
                System.out.print(root.data);
                root.printNode();
                System.out.println();
            }
        }

然后，在Node类中做节点的输出：

//输出所有节点
            public void printNode() {
        
                if (this.next != null) {
        
                    System.out.print("-->" + this.next.data);
                    this.next.printNode();
                }
            }

**8、取出全部数据：**

*  public 数据 \[\] toArray()

对于链表的这种数据结构，最为关键的是两个操作：删除、取得全部数据。

在LinkList类之中需要定义一个操作数组的脚标：

private int foot = 0;      // 操作返回数组的脚标

在LinkList类中定义返回数组，必须以属性的形式出现，只有这样，Node类才可以访问这个数组并进行操作：

private String [] retData ;       // 返回数组

在LinkList类之中增加toArray()的方法：

//方法：获取全部数据
        public String[] toArray() {
        
            if (this.size == 0) {
        
                return null; // 没有数据
            }
            this.foot = 0;       // 清零
            this.retData = new String[this.size];     // 开辟数组大小
            this.root.toArrayNode();
            return this.retData;
        }

修改Node类的操作，增加toArrayNode()方法：

//获取全部数据
            public void toArrayNode() {
        
                LinkList.this.retData[LinkList.this.foot++] = this.data;
                if (this.next != null) {
        
                    this.next.toArrayNode();
                }
            }

不过，按照以上的方式进行开发，每一次调用toArray()方法，都要重复的进行数据的遍历，如果在数据没有修改的情况下，这种做法是一种非常差的做法，最好的做法是增加一个修改标记，如果发现数据增加了或删除的话，表示要重新遍历数据。

private boolean changeFlag = true ;
     // changeFlag == true：数据被更改了，则需要重新遍历
    // changeFlag == false：数据没有更改，不需要重新遍历

然后，我们修改LinkList类中的toArray()方法：（其他代码保持不变）

//方法：获取全部数据
        public String[] toArray() {
        
            if (this.size == 0) {
        
                return null; // 没有数据
            }
            this.foot = 0;       // 清零
            if (this.changeFlag == true) {
                  // 内容被修改了，需要重新取
                this.retData = new String[this.size];     // 开辟数组大小
                this.root.toArrayNode();
            }
            return this.retData;
        }

**9、根据索引位置取得数据：**

*  public 数据 get(int index)

在一个链表之中会有多个节点保存数据，现在要求可以取得指定节点位置上的数据。但是在进行这一操作的过程之中，有一个小问题：如果要取得数据的索引超过了数据的保存个数，那么是无法取得的。

在LinkList类之中，增加一个get()方法：

//方法：根据索引取得数据
        public String get(int index) {
        
            if (index > this.size) {
                 // 超过个数
                return null;          // 返回null
            }
            this.foot = 0;       // 操作foot来定义脚标
            return this.root.getNode(index);
        }

在Node类之中配置getNode()方法：

//根据索引位置获取数据
            public String getNode(int index) {
        
                if (LinkList.this.foot++ == index) {
             // 当前索引为查找数值
                    return this.data;
                } else {
        
                    return this.next.getNode(index);
                }
            }

**10、清空链表：**

*  public void clear()

所有的链表被root拽着，这个时候如果root为null，那么后面的数据都会断开，就表示都成了垃圾：

//清空链表
        public void clear() {
        
            this.root = null;
            this.size = 0;
        }

总结：

上面的10条方法中，LinkList的完整代码如下：

/**
     * Created by smyhvae on 2015/8/27.
     */
    
    public class LinkList {
        
    
        private int size;
        private Node root; //定义一个根节点
    
        private int foot = 0;      // 操作返回数组的脚标
        private String[] retData;       // 返回数组
        private boolean changeFlag = true;
        // changeFlag == true：数据被更改了，则需要重新遍历
        // changeFlag == false：数据没有更改，不需要重新遍历
    
    
        //添加数据
        public boolean add(String data) {
        
    
            if (data == null) {
             // 如果添加的是一个空数据，那增加失败
                return false;
            }
    
            // 将数据封装为节点，目的：节点有next可以处理关系
            Node newNode = new Node(data);
            // 链表的关键就在于根节点
            if (root == null) {
          //如果根节点是空的，那么新添加的节点就是根节点。(第一次调用add方法时，根节点当然是空的了)
                root = newNode;
            } else {
        
                root.addNode(newNode);
    
            }
    
            this.size++;
            return true;
    
        }
    
    
        //方法：增加一组数据
        public boolean addAll(String data[]) {
             // 一组数据
            for (int x = 0; x < data.length; x++) {
        
                if (!this.add(data[x])) {
         // 只要有一次添加不成功，那就是添加失败
                    return false;
                }
            }
            return true;
        }
    
        //方法：删除数据
        public boolean remove(String data) {
         //要删除的节点，假设每个节点的data都不一样
    
            if (!this.contains(data)) {
         //要删除的数据不存在
                return false;
            }
    
            if (root != null) {
        
                if (root.data.equals(data)) {
          //说明根节点就是需要删除的节点
                    root = root.next;  //让根节点的下一个节点成为根节点，自然就把根节点顶掉了嘛（不像数组那样，要将后面的数据在内存中整体挪一位）
                } else {
          //否则
                    root.removeNode(data);
                }
            }
            size--;
            return true;
    
        }
    
        //输出所有节点
        public void print() {
        
            if (root != null) {
        
                System.out.print(root.data);
                root.printNode();
                System.out.println();
            }
        }
    
    
        //方法：获取全部数据
        public String[] toArray() {
        
            if (this.size == 0) {
        
                return null; // 没有数据
            }
            this.foot = 0;       // 清零
            this.retData = new String[this.size];     // 开辟数组大小
            this.root.toArrayNode();
            return this.retData;
        }
    
    
        //获取数据的长度
        public int size() {
        
            return this.size;
        }
    
        //判断是否为空链表
        public boolean isEmpty() {
        
            return this.size == 0;
        }
    
        //清空链表
        public void clear() {
        
            this.root = null;
            this.size = 0;
        }
    
    
        //查询数据是否存在
        public boolean contains(String data) {
              // 查找数据
            // 根节点没有数据，查找的也没有数据
            if (this.root == null || data == null) {
        
                return false;        // 不需要进行查找了
            }
            return this.root.containsNode(data);        // 交给Node类处理
        }
    
    
        //方法：根据索引取得数据
        public String get(int index) {
        
            if (index > this.size) {
                 // 超过个数
                return null;          // 返回null
            }
            this.foot = 0;       // 操作foot来定义脚标
            return this.root.getNode(index);
        }
    
    
        //定义一个节点内部类（假设要保存的数据类型是字符串）
        //比较好的做法是，将Node定义为内部类，在这里面去完成增删、等功能，然后由LinkList去调用增、删的功能
        class Node {
        
            private String data;
            private Node next;  //next表示：下一个节点对象（单链表中）
    
            public Node(String data) {
        
                this.data = data;
            }
    
            //添加节点
            public void addNode(Node newNode) {
        
    
                //下面这段用到了递归，需要反复理解
                if (this.next == null) {
           // 递归的出口：如果当前节点之后没有节点，说明我可以在这个节点后面添加新节点
                    this.next = newNode;   //添加新节点
                } else {
        
                    this.next.addNode(newNode);  //向下继续判断，直到当前节点之后没有节点为止
    
                }
            }
    
    
            //判断节点是否存在
            public boolean containsNode(String data) {
              // 查找数据
                if (data.equals(this.data)) {
             // 与当前节点数据吻合
                    return true;
                } else {
               // 与当前节点数据不吻合
                    if (this.next != null) {
           // 还有下一个节点
                        return this.next.containsNode(data);
                    } else {
               // 没有后续节点
                        return false;        // 查找不到
                    }
                }
            }
    
    
            //删除节点
            public void removeNode(String data) {
        
                if (this.next != null) {
        
                    if (this.next.data.equals(data)) {
        
                        this.next = this.next.next;
                    } else {
        
                        this.next.removeNode(data);
                    }
                }
    
            }
    
            //输出所有节点
            public void printNode() {
        
                if (this.next != null) {
        
                    System.out.print("-->" + this.next.data);
                    this.next.printNode();
                }
            }
    
            //获取全部数据
            public void toArrayNode() {
        
                LinkList.this.retData[LinkList.this.foot++] = this.data;
                if (this.next != null) {
        
                    this.next.toArrayNode();
                }
            }
    
    
            //根据索引位置获取数据
            public String getNode(int index) {
        
                if (LinkList.this.foot++ == index) {
             // 当前索引为查找数值
                    return this.data;
                } else {
        
                    return this.next.getNode(index);
                }
            }
    
    
        }
    }

[Link 1]: https://blog.csdn.net/weixin_44688973/article/details/119849214
[8de48176434243aea4dca153b0d91ca9.png]: https://img-blog.csdnimg.cn/8de48176434243aea4dca153b0d91ca9.png
[d0201102c34746f18620ba34ea10a3e6.png]: https://img-blog.csdnimg.cn/d0201102c34746f18620ba34ea10a3e6.png