java实现单链表和双链表数据结构

首先定义一个接口, 规范单链表和双链表常用的基本操作:

public interface linkedList {
    
    int size();

    
    boolean isEmpty();

    
    T get(int index);

    
    T getFirst();

    
    T getLast();

    
    void insert(int index, T data);

    
    void insertFirst(T data);

    
    void append(T data);

    
    void del(int index);

    
    void deleteFirst();

    
    void deleteLast();


}

单链表实现:

public class SinglelinkedList implements linkedList {
    
    private Node nodeHead;

    
    private int nodeCount;

    public SinglelinkedList() {
        nodeHead = new Node(null, null);
        nodeCount = 0;
    }

    
    @Override
    public boolean isEmpty() {
        return nodeCount == 0;
    }

    
    @Override
    public int size() {
        return nodeCount;
    }

    
    private Node getNode(int index) {
        if (nodeCount < 0 || index >= nodeCount) {
            throw new IndexOutOfBoundsException();
        }
        Node node = nodeHead.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    
    @Override
    public T get(int index) {
        return getNode(index).value;
    }

    
    @Override
    public T getFirst() {
        return getNode(0).value;
    }

    
    @Override
    public T getLast() {
        return getNode(nodeCount - 1).value;
    }

    
    @Override
    public void insert(int index, Object data) {
        if (index == 0) {
            Node node = new Node<>(nodeHead.next, (T) data);
            nodeHead.next = node;
            nodeCount++;
            return;
        }

        Node lNode = getNode(index - 1);
        Node node = new Node<>(lNode.next, (T) data);
        lNode.next = node;
        nodeCount++;
        return;
    }

    
    @Override
    public void append(Object data) {
        insert(nodeCount, (T) data);
    }

    
    @Override
    public void insertFirst(Object data) {
        insert(0, (T) data);
    }

    
    @Override
    public void del(int index) {
        Node node = getNode(index);
        if (index == 0) {
            nodeHead.next = node.next;
            node = null;
            nodeCount--;
            return;
        }
        getNode(index - 1).next = node.next;
        node = null;
        nodeCount--;
        return;
    }

    
    @Override
    public void deleteFirst() {
        del(0);
    }

    
    @Override
    public void deleteLast() {
        del(nodeCount - 1);
    }


    
    
    private class Node {
        // 后继
        private Node next;
        // 数据
        private T value;

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

}

 双链表实现:

public class DoublelinkedList implements linkedList {
    
    private Node nodeHead;
    
    private int nodeCount;

    
    public DoublelinkedList() {
        // 初始化链表, 创建表头(表头不存储数据)
        nodeHead = new Node(null, null, null);
        // 初始化前驱和后继, 默认指向自身
        nodeHead.prev = nodeHead.next = nodeHead;
        // 初始化节点个数, 0个
        nodeCount = 0;
    }

    
    @Override
    public int size() {
        return nodeCount;
    }

    
    @Override
    public boolean isEmpty() {
        return nodeCount == 0;
    }

    
    private Node getNode(int index) {
        if (index < 0 || index >= nodeCount) {
            throw new IndexOutOfBoundsException();
        }

        if (index <= nodeCount / 2) {
            
            // 初始化指向第一个Node
            Node node = nodeHead.next;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            
            // 初始化指向最后一个Node
            Node rNode = nodeHead.prev;
            // 查找范围长度
            int rLength = nodeCount - index - 1;
            for (int j = 0; j < rLength; j++) {
                rNode = rNode.prev;
            }

            return rNode;
        }


    }

    
    @Override
    public T get(int index) {
        return getNode(index).value;
    }

    
    @Override
    public T getFirst() {
        return getNode(0).value;
    }

    
    @Override
    public T getLast() {
        return getNode(nodeCount - 1).value;
    }

    
    @Override
    public void insert(int index, Object data) {
        // 若初始化时除头节点外没有其他节点
        if (index == 0) {
            // 新建节点
            Node node = new Node<>(nodeHead, nodeHead.next, (T) data);
            nodeHead.next = node;
            node.next.prev = node;
            nodeCount++;
            return;
        }

        Node inode = getNode(index);
        Node tNode = new Node<>(inode.prev, inode, (T) data);
        inode.prev.next = tNode;
        inode.prev = tNode;
        nodeCount++;
        return;
    }

    
    @Override
    public void insertFirst(Object data) {
        insert(0, (T) data);
    }

    
    @Override
    public void append(Object data) {
        Node node = new Node<>(nodeHead.prev, nodeHead, (T) data);
        nodeHead.prev.next = node;
        nodeHead.prev = node;

        nodeCount++;
    }

    
    @Override
    public void del(int index) {
        Node node = getNode(index);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node = null;
        nodeCount--;
    }

    
    @Override
    public void deleteFirst() {
        del(0);
    }

    
    @Override
    public void deleteLast() {
        del(nodeCount - 1);
    }

    
    
    private class Node {
        // 前驱
        public Node prev;
        // 后继
        public Node next;
        // 数据
        public T value;

        public Node(Node prev, Node next, T data) {
            this.prev = prev;
            this.next = next;
            this.value = data;
        }
    }
    
}

 使用:

public class HuzzTest {
    public static void main(String[] args) {
        linkedList singlelinkedList = new SinglelinkedList<>();
        linkedList doublelinkedList = new DoublelinkedList<>();
        
        for (int i = 0; i < 10; i++) {
            singlelinkedList.append(i);
            doublelinkedList.append(i);
        }
        
        singlelinkedList.append(45);
        singlelinkedList.del(5);
        singlelinkedList.isEmpty();
        singlelinkedList.insertFirst(90);
        doublelinkedList.get(6);
        doublelinkedList.size();
    }
}

 虽然java提供了数据链表的工具类, 但自己学习过程中手工编写还是比较有收获的, 能加深对数据结构的认识.