Java数据结构之手写单链表-蒲公英云

Java数据结构之手写单链表

简单实现单链表

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; // 指针后移一个结点
        }
    }
}