一、单向链表

单向链表的普通实现

Java实现:

package linkedlist;
/**
 * 单向链表的普通实现
 *
 * @param <E> E
 * @author ZZX
 */
public class SinglyLinkedList<E> implements LinkedList<E> {
    /**
     * 节点内部类
     */
    private class Node {

        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }

    }

    /**
     * 虚拟头节点，避免逻辑上区别处理头部节点
     */
    private Node dummyHead;

    private int size;

    public SinglyLinkedList() {
        dummyHead = new Node();
        size = 0;
    }

    public boolean add(int index, E e) {
        if (index < 0 || index > size) {
            return false;
        }

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;
        prev.next = new Node(e, prev.next);
        size++;
        return true;
    }

    public E findFirst() {
        return dummyHead.next.e;
    }

    public void addFirst(E e) {
//        Node node = new Node(e);
//        node.next = head;
//        head = node;
        add(0, e);
    }

    public void addLast(E e) {
        add(size, e);
    }

    public E get(int index) {
        return getNode(index).next.e;
    }

    public void set(int index, E e) {
        getNode(index).next.e = e;
    }

    public boolean contains(E e) {
        Node curNode = dummyHead.next;
        while (curNode != null) {
            if (e.equals(curNode.e)) {
                return true;
            }
            curNode = curNode.next;
        }
        return false;
    }

    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法index");
        }
        Node prevNode = getNode(index);
        Node retNode = prevNode.next;
        prevNode.next = retNode.next;
        retNode.next = null;
        size--;
        return retNode.e;
    }

    private Node getNode(int index) {
        Node prevNode = dummyHead;
        for (int i = 0; i < index; i++) {
            prevNode = prevNode.next;
        }
        return prevNode;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: [");
        Node curNode = dummyHead.next;
        while (curNode != null) {
            sb.append(curNode.e + "-->");
            curNode = curNode.next;
        }
        sb.append("Null]");
        return sb.toString();
    }
}

Kotlin实现：

//ToDo

单向链表的递归实现

Java实现:

package linkedlist;

import javafx.util.Pair;

/**
 * 单向链表的递归实现
 *
 * @param <E> E
 * @author ZZX
 */
public class SinglyLinkedList<E> implements LinkedList<E> {
    /**
     * 节点内部类
     */
    private class Node {

        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head;

    private int size;

    public SinglyLinkedList() {
        head = null;
        size = 0;
    }

    public boolean add(int index, E e) {
        if (index < 0 || index > size) {
            return false;
        }
        head = add(head, index, e);
        size++;
        return true;
    }

    private Node add(Node node, int index, E e) {
        if (0 == index) {
            return new Node(e, node);
        }
        node.next = add(node.next, index - 1, e);
        return node;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public E get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法Index");
        }
        return get(head, index);
    }

    public E get(Node node, int index) {
        if (0 == index) {
            return node.e;
        }
        return get(node.next, index - 1);
    }

    public void set(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法Index");
        }
        set(head, index, e);
    }

    private void set(Node node, int index, E e) {
        if (0 == index) {
            node.e = e;
            return;
        }
        set(node.next, index - 1, e);
    }

    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法Index");
        }
        Pair<Node, E> res = remove(head, index);
        return res.getValue();
    }

    private Pair<Node, E> remove(Node node, int index) {
        if (0 == index) {
            return new Pair<>(node.next, node.e);
        }
        Pair<Node, E> res = remove(node.next, index - 1);
        node.next = res.getKey();
        return new Pair<>(node, res.getValue());
    }


    public E findFirst() {
        return head.next.e;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node curNode = head;
        while (curNode != null) {
            sb.append(curNode).append("-->");
            curNode = curNode.next;
        }
        return sb.append("NULL").toString();
    }

    public static void main(String[] args) {
        SinglyLinkedList<Integer> singlyLinkedList = new SinglyLinkedList<>();
        for (int i = 0; i < 10; i++) {
            singlyLinkedList.addFirst(i);
        }
        System.out.println(singlyLinkedList);
        singlyLinkedList.remove(2);
        System.out.println(singlyLinkedList);
        singlyLinkedList.set(3, 129384);
        System.out.println(singlyLinkedList);
        System.out.println(singlyLinkedList.get(3));
    }
}

二、双向链表

Java实现：

//ToDo

Kotlin实现:

//TODO

三、循环链表

Java实现：

//ToDo

Kotlin实现:

//TODO

• Tips：Java/Kotlin链表接口

//Java
package linkedlist;

/**
 * 链表增删改查接口
 * @author ZhuZongxing
 * @param <E> 泛型
 */
public interface LinkedList<E> {
    boolean add(int index, E e);

    E remove(int index);

    void set(int index, E e);

    E get(int index);

    int getSize();

    boolean isEmpty();
}