欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-16 15:30:16
...

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

/**
 * @Author Huzz
 * @Created 2021-10-09 17:49
 */
public interface LinkedList<T> {
    /**
     * 节点长度
     * @return
     */
    int size();

    /**
     * 返回链表是否为空
     * @return 空:true | 非空:false
     */
    boolean isEmpty();

    /**
     * 获取第index位置的节点的值
     * @param index
     * @return
     */
    T get(int index);

    /**
     * 获取第1个节点的值
     * @return
     */
    T getFirst();

    /**
     * 获取最后一个节点的值
     * @return
     */
    T getLast();

    /**
     * 将节点插入到第index位置之前
     * @param index
     * @param data 数据
     */
    void insert(int index, T data);

    /**
     * 将节点插入第一个节点处
     * @param data 数据
     */
    void insertFirst(T data);

    /**
     * 将节点追加到链表的末尾
     * @param data
     */
    void append(T data);

    /**
     * 删除index位置的节点
     * @param index
     */
    void del(int index);

    /**
     * 删除第一个节点
     */
    void deleteFirst();

    /**
     * 删除最后一个节点
     */
    void deleteLast();


}

单链表实现:

/**
 * 单向链表
 *
 * @Author Huzz
 * @Created 2021-10-09 14:49
 */
public class SingleLinkedList<T> implements LinkedList {
    /**
     * 表头
     */
    private Node<T> 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;
    }

    /**
     * 查找节点
     *
     * @param index
     * @return
     */
    private Node<T> getNode(int index) {
        if (nodeCount < 0 || index >= nodeCount) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> 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;
    }

    /**
     * 查找第一个节点
     *
     * @return
     */
    @Override
    public T getFirst() {
        return getNode(0).value;
    }

    /**
     * 查找最后一个节点
     *
     * @return
     */
    @Override
    public T getLast() {
        return getNode(nodeCount - 1).value;
    }

    /**
     * 在指定位置前插入节点
     *
     * @param index
     * @param data
     */
    @Override
    public void insert(int index, Object data) {
        if (index == 0) {
            Node<T> node = new Node<>(nodeHead.next, (T) data);
            nodeHead.next = node;
            nodeCount++;
            return;
        }

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

    /**
     * 在链表末尾添加节点
     *
     * @param data
     */
    @Override
    public void append(Object data) {
        insert(nodeCount, (T) data);
    }

    /**
     * 在第一个节点前插入一个节点
     *
     * @param data
     */
    @Override
    public void insertFirst(Object data) {
        insert(0, (T) data);
    }

    /**
     * 删除节点
     *
     * @param index
     */
    @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);
    }


    /**
     * ======================================定义节点==============================================
     */
    /**
     * 单链表节点定义
     *
     * @param <T>
     */
    private class Node<T> {
        // 后继
        private Node<T> next;
        // 数据
        private T value;

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

}

 双链表实现:

/**
 * 双向链表
 *
 * @Author Huzz
 * @Created 2021-10-09 8:54
 */
public class DoubleLinkedList<T> implements LinkedList {
    /**
     * 表头
     */
    private Node<T> nodeHead;
    /**
     * 节点个数
     */
    private int nodeCount;

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

    /**
     * 节点长度
     *
     * @return
     */
    @Override
    public int size() {
        return nodeCount;
    }

    /**
     * 返回链表是否为空
     *
     * @return 空:true | 非空:false
     */
    @Override
    public boolean isEmpty() {
        return nodeCount == 0;
    }

    /**
     * 获取第index位置的节点
     *
     * @param index
     * @return
     */
    private Node<T> getNode(int index) {
        if (index < 0 || index >= nodeCount) {
            throw new IndexOutOfBoundsException();
        }

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

            return rNode;
        }


    }

    /**
     * 获取第index位置的节点的值
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        return getNode(index).value;
    }

    /**
     * 获取第1个节点的值
     *
     * @return
     */
    @Override
    public T getFirst() {
        return getNode(0).value;
    }

    /**
     * 获取最后一个节点的值
     *
     * @return
     */
    @Override
    public T getLast() {
        return getNode(nodeCount - 1).value;
    }

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

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

    /**
     * 将节点插入第一个节点处
     *
     * @param data
     */
    @Override
    public void insertFirst(Object data) {
        insert(0, (T) data);
    }

    /**
     * 将节点追加到链表的末尾
     *
     * @param data
     */
    @Override
    public void append(Object data) {
        Node<T> node = new Node<>(nodeHead.prev, nodeHead, (T) data);
        nodeHead.prev.next = node;
        nodeHead.prev = node;

        nodeCount++;
    }

    /**
     * 删除index位置的节点
     *
     * @param index
     */
    @Override
    public void del(int index) {
        Node<T> 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);
    }

    /** ======================================定义节点============================================== */
    /**
     * 双向链表节点定义
     *
     * @param <T>
     */
    private class Node<T> {
        // 前驱
        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;
        }
    }
    /** =========================================================================================== */
}

 使用:

/**
 * @Author Huzz
 * @Created 2021-10-09 18:51
 */
public class HuzzTest {
    public static void main(String[] args) {
        LinkedList<Integer> singleLinkedList = new SingleLinkedList<>();
        LinkedList<Integer> 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提供了数据链表的工具类, 但自己学习过程中手工编写还是比较有收获的, 能加深对数据结构的认识.