【数据结构】使用 Java 实现单链表

亦凉 2023-02-19 08:27 18阅读 0赞

## 链表 ##

**链表定义**

> n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

![format_png][]

**链表优点**

*  插入删除快

**链表缺点**

*  存取速度慢

## Java 实现单链表 ##

public class MyNode { 
    
        /** * 链表保存的数据 */
        private int data;
    
        /** * 链表的下一个节点 */
        private MyNode next;
    
        /** * 构造函数 * * @param data */
        public MyNode(int data) { 
            this.data = data;
        }
    
        /** * 添加节点 * * @param myNode */
        public MyNode append(MyNode myNode) { 
            // 取出当前节点
           MyNode currentNode = this;
           // 循环判断是否为最后一个节点
           while (true) { 
               // 取出下一个节点
               MyNode nextNode = currentNode.next;
               // 如果为空，说明为最后一个节点
               if (nextNode == null) { 
                   break;
               } else { 
                   // 否则继续寻找下一个节点
                   currentNode = nextNode;
               }
           }
           // 最后一个节点的 next 赋值新添加的元素
           currentNode.next = myNode;
           return myNode;
        }
    
        /** * 删除下一个节点 */
        public void removeNext() { 
            // 记录下下个节点的信息
            MyNode nextNode = this.next.next;
            // 删除下一个节点
            this.next = nextNode;
        }
    
        /** * 显示链表 */
        public void show() { 
            MyNode currentNode = this;
            while (true) { 
                if (currentNode != null) { 
                    System.out.print(currentNode.getData() + "\t");
                    currentNode = currentNode.next;
                } else { 
                  break;
                }
            }
            System.out.println();
        }
    
        /** * 插入一个节点 * * @param myNode */
        public void insert(MyNode myNode) { 
            // 记录下一节点信息
            MyNode nextNode = this.next;
            // 下一个节点指向要添加的节点
            this.next = myNode;
            // 连接原来的节点
            myNode.next = nextNode;
        }
    
        /** * 获取当前节点的数据 * * @return */
        public int getData() { 
            return this.data;
        }
    
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly95dXUtYmxvZy5vc3MtY24tc2hlbnpoZW4uYWxpeXVuY3MuY29tL25vZGUuanBn?x-oss-process=image/format,png