Java数据结构之手写单链表

谁借莪１个温暖的怀抱￠ 2024-04-06 11:31 60阅读 0赞

简单实现单链表

package com.mmg;
    
    /**
     * 节点类
     * @author MUMANGGUO
     */
    public class Node {
    
        public Object data;
        public Node next;
    
        public Node(Object values, Node next) {
            super();
            this.data = values;
            this.next = next;
        }
    
        public Node() {
            this(null, null);
        }
    
        public String toString() {
            return this.data.toString();
        }
    }

package com.mmg;
    
    public class MySinglyLinkedList {
        // 单链表的头指针，指向头结点
        public Node head;
    
        // 构造空单链表
        public MySinglyLinkedList() {
            head = new Node(); // 创建头结点，data和next的值均为null
        }
    
        // 构造单链表，由数组提供元素
        public MySinglyLinkedList(Object[] values) {
            this(); // 创建只有头结点的单链表
            Node rear = this.head; // rear指向单链表的尾结点
            for (int i = 0; i < values.length; i++) {
                rear.next = new Node(values[i], null); // 尾插法，创建结点链接入rear结点之后
                rear = rear.next; // rear指向新的尾结点
            }
        }
    
        public Object get(int i) {// 返回元素ai，若i越界，返回null
            int j = 0;
            Node p = this.head.next;
            for (i = 0; p != null && j < i; j++) { // 遍历单链表，寻找第i个结点
                p = p.next;
            }
            return (i >= 0 && p != null) ? p.data : null;// 若p指向ai，返回其data值
        }
    
        public void set(int i, Object obj) {// 设置元素ai的值，即设置其data域的值为t
            int j = 0;
            Node p = this.head.next;
            for (i = 0; p != null && j < i; j++) { // 遍历单链表，寻找结点ai
                p = p.next;
            }
            if (i >= 0 && p != null) {
                p.data = obj; // 将ai的data域设置为t
            }
        }
    
        public int add(Object obj) {
            return add(this.length(), obj);
        }
    
        public int add(int i, Object t) {
    // 在a(i)的位置插入元素t，若插入成功，返回i，否则 ，返回-1
            int j = 0;
            if (t == null)
                throw new NullPointerException("不能插入空对象！");// 抛出空对象异常
            Node p = this.head;
            while (p.next != null && j < i) { // 寻找a(i-1)结点
                p = p.next;
                j++;
            }
            if (p != null && j == i) { // 找到a(i-1)结点
                Node s = new Node(t, p.next); // 建立新结点，数据域为元素t，地址域为p.next
                p.next = s; // 在p之后插入新结点
                return i; // 插入成功，返回i
            } else {
                return -1; // 插入失败，返回-1
            }
        }
    
        // 删除结点a(i)
        public Object remove(int i) {
            int j = 0;
            Node p = this.head;
            while (p.next != null && j < i) { // 寻找a(i-1)结点
                p = p.next;
                j++;
            }
            if (p.next != null && j == i) { // a(i)结点存在
                Object old = p.next.data; // 保存待删除结点的数据域
                p.next = p.next.next; // 删除结点，包括开始结点、中间结点和尾结点删除
                return old; // 返回已删除结点的数据域
            } else {
                return null; // i越界，返回null
            }
        }
    
        // 判断单链表中是否包含key元素
        public boolean contains(Object key) {
            Node p = this.head.next;
            for (; p != null; p = p.next) { // 遍历单链表
                if (p.data.equals(key)) {
                    return true;
                }
            }
            return false;
        }
    
        // 在单链表查找首次出现的与key相等元素，返回元素位置，若不存在，则返回-1
        public int indexOf(Object key) {
            int i = 0;
            Node p = this.head.next;
            for (; p != null; p = p.next) { // 遍历单链表
                if (p.data.equals(key)) {
                    return i;
                }
                i++;
            }
            return -1;
        }
    
        // 返回单链表的长度
        public int length() {
            int n = 0;
            Node p = this.head.next;
            while (p != null) {
                n++;
                p = p.next;
            }
            return n;
        }
    
        // 清空单链表
        public void clear() {
            this.head.next = null;
        }
    
        // 判断单链表是否为空
        public boolean isEmpty() {
            return this.head.next == null;
        }
    
        // 遍历单链表
        public void printList() {
            Node p = this.head.next;
            while (p != null) {
                System.out.println(p.data); // 输出结点的数据域
                p = p.next; // 指针后移一个结点
            }
        }
    }

可以自己写一个测试类进行测试