自己实现一个单链表

自己实现一个单链表

别人怀宝剑,我有笔如刀。

在上一篇文章中,我们讲了 Java 的 LinkedList 的源码,今天我们就自己来实现一个单链表。

话不多说,直接上代码。

public class SingleLinkedList<T> {

    private static final int DEFAULT_LIST_SIZE = 0;

    // 头结点
    private Node<T> head;
    // 尾结点
    private Node<T> tail;

    private int length = DEFAULT_LIST_SIZE;

    // 结点Node 单链表: 只包含一个value和next
    public static class Node<T> {
        // 结点值
        private T value;
        // 下一个结点
        private Node<T> next;

        public Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }

        // 只是为了方便打印
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

    /**
     * 添加头结点
     * @param value 结点值
     * @return 头结点
     */
    public Node<T> addHead(T value) {
        Node<T> node = new Node<>(value, null);
        node.next = head; // 只需要将新结点的next指向原头结点就可以了
        head = node; // 更新头结点
        length++; // 长度加1
        return node;
    }

    /**
     * 添加尾结点
     * @param value 结点值
     * @return 尾结点
     */
    public Node<T> addTail(T value) {
        if (head == null) {
            head = new Node<>(value, null);
            length++;
            tail = head;
            return head;
        }
        Node<T> node = add(value, length);
        tail = node;
        return node;
    }

    /**
     * 在尾部添加新结点
     * @param value 结点值
     * @return 新结点的值
     */
    public Node<T> add(T value, int index) {
        if (index > length || index < 1 ) {
            return null;
        }
        Node<T> newNode = new Node<>(value, null); // 创建一个新结点
        int curIndex = 1;
        Node<T> curNode = head; // 从头结点开始遍历
        while (curNode.next != null) {
            if (curIndex == index) {
                break; // 不在里面删除的主要原因是避免curNode是尾结点的是时候,不能进来
            }
            curNode = curNode.next;
            curIndex++;
        }
        newNode.next = curNode.next;
        curNode.next = newNode;
        length++;
        return null;
    }

    /**
     * 删除头结点
     * @return 头结点的值
     */
    public T removeHead() {
        if (head == null) {
            return null;
        }
        T value = head.value;
        head = head.next;
        if (length == 1) {
            tail = null;
        }
        length--;
        return value;
    }

    /**
     * 删除尾结点
     * @return 尾结点的值
     */
    public T removeTail() {
        if (head == null || length == 1) {
            T value = head == null ? null : head.value;
            head = null;
            length--;
            return value;
        }
        Node<T> preNode = head;
        Node<T> curNode = head.next;
        while (curNode.next != null) {
            preNode = curNode;
            curNode = curNode.next;
        }
        preNode.next = null;
        length--;
        tail = preNode;
        return curNode.value;

    }

    /**
     * 删除指定结点
     * @param index 序号
     * @return 结点的值
     */
    public T remove(int index) {
        if (index > length || length < 1 || head == null) {
            return null;
        }
        if (index == 1) { // 序号为1,直接返回头结点
            return removeHead();
        }

        int curIndex = 2; // 当前序号, 因为上面已经返回了头结点,所以从第二个结点开始
        Node<T> preNode = head; // 记录上一个结点,便于删除
        Node<T> curNode = head.next; // 当前需要删除的绩点
        while (curNode != null) {  // 遍历
            if (curIndex == index) { // 当前序号为需要删除的序号的时候
                preNode.next = curNode.next; // 直接将当前结点next赋值前结点的next, 删除结点的常规操作
                if (index == length) {  // 如果序号的长度等于链表长度
                    tail = preNode;
                }
                length--;   // 链表-1
                return curNode.value;
            }
            preNode = curNode;  // 为下一个遍历做准备, 当前结点变成前一个结点
            curNode = curNode.next; // 获取下一个结点
            curIndex++;
        }
        return null;
    }

    /**
     * 获取指定序号的结点值
     * @param index 序号
     * @return 值
     */
    public T get(int index) {
        if (index > length || index < 1 || head == null) {
            return null;
        }
        if (index == 1) { // 头结点,不需要遍历
            return head.value;
        }
        if (index == length) { // 尾结点,也不需要遍历了
            return tail.value;
        }
        int tempIndex = 2; // 当前序号, 因为上面已经返回了头结点,所以从第二个结点开始
        Node<T> curNode = head.next; // 当前序号
        while (curNode.next != null) {
            if (tempIndex == index) { // 找到了指定序号的结点
                return curNode.value;
            }
            curNode = curNode.next; // 获取写一个结点
            tempIndex++;
        }
        return null;
    }

    public int size() {
        return length;
    }


    public Node<T> getHead() {
        return head;
    }

    public void setHead(Node<T> head) {
        this.head = head;
    }

    public Node<T> getTail() {
        return tail;
    }

    public void setTail(Node<T> tail) {
        this.tail = tail;
    }

    /**
     * 打印链表
     */
    public void printLinkedList() {
        StringBuilder sb = new StringBuilder();
        if (head == null) {
            System.out.println("empty list");
            return;
        }
        Node<T> node = head;
        while (node.next != null) {
            sb.append(node.value).append("->");
            node = node.next;
        }
        sb.append(node.value);
        System.out.println(sb.toString());

    }
}

代码测试

public static void main(String[] args) {
    SingleLinkedList<Integer> linkedList = new SingleLinkedList<>();
    linkedList.printLinkedList();
    linkedList.addTail(1);
    linkedList.addTail(2);
    linkedList.addTail(3);
    linkedList.addTail(4);
    linkedList.addTail(5);
    linkedList.addTail(6);
    linkedList.addHead(0);
    System.out.print("原始链表: ");
    linkedList.printLinkedList();
    System.out.println("原始链表长度: " + linkedList.size());
    int index = linkedList.size() - 2;
    linkedList.remove(index);
    System.out.print("删除第" + index + "个结点后的链表: ");
    linkedList.printLinkedList();
    System.out.println("删除第" + index + "个结点后的链表长度: " + linkedList.size());
    linkedList.removeHead();
    System.out.print("删除头结点后的链表: ");
    linkedList.printLinkedList();
    System.out.println("删除头结点后的链表长度: " + linkedList.size());
    System.out.println("头结点" + linkedList.getHead());
    System.out.println("尾结点" + linkedList.getTail());
    linkedList.removeTail();
    System.out.print("删除尾结点后的链表: ");
    linkedList.printLinkedList();
    System.out.println("删除尾结点后的链表长度: " + linkedList.size());
    int getIndex = linkedList.size() - 1;
    System.out.println("获取第" + getIndex +  "个结点: " + linkedList.get(getIndex));
    int nullIndex = linkedList.size() + 1;
    System.out.println("获取第" + nullIndex +  "个结点: " + linkedList.get(nullIndex));
    System.out.println("尾结点" + linkedList.getTail());
}

代码输出

代码输出

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://baozi.fun/2020/02/16/realize-a-single-linkedlist

Buy me a cup of coffee ☕.