双向链表Java实现

曾经终败给现在 2022-06-02 09:59 165阅读 0赞

LinkedList：

/** * * @ClassName: LinkedList * @Description: 双向链表 * @author xiaomu * @date 2018年1月15日 上午11:46:20 * * @param <T> */
    public class LinkedList<T> implements List<T> {
        private int size = 0;
        private Node<T> first;
        private Node<T> last;
    
        public LinkedList() {
            first = new Node<T>();
            last = new Node<T>();
            first.setNextNode(last);
            last.setPreNode(first);
        }
    
        @Override
        public boolean isEmpty() {
            return first.getNextNode() == last && last.getPreNode() == first;
        }
    
        @Override
        public int lenth() {
            return size;
        }
    
        @Override
        public T get(int index) {
            if (index < 1 || index > size) {
                System.out.println("index 范围异常");
                return null;
            }
            return getNode(index).getItem();
        }
    
        private Node<T> getNode(int index) {
            if (index < 1 || index > size) {
                System.out.println("index 范围异常");
                return null;
            }
            Node<T> node = first;
            while (index > 0) {
                index--;
                node = node.getNextNode();
            }
            return node;
        }
    
        @Override
        public int indexOf(T elem) {
            if (null == elem) {
                return -1;
            }
            int i = 0;
            Node<T> node = first;
            while (node.getNextNode() != null) {
                node = node.getNextNode();
                i++;
                if (node.getItem() == elem) {
                    return i;
                }
            }
            return -1;
        }
    
        @Override
        public void insert(int index, T elem) {
            if (index < 1 || index > size) {
                System.out.println("index 范围异常");
                return;
            }
            Node<T> newNode = new Node<T>(elem);
            // 获取指定位置的前一个节点
            Node<T> preNode = getNode(index).getPreNode();
            preNode.getNextNode().setPreNode(newNode);
            newNode.setNextNode(preNode.getNextNode());
            preNode.setNextNode(newNode);
            newNode.setPreNode(preNode);
            size++;
        }
    
        @Override
        public T remove(int index) {
            if (index < 1 || index > size) {
                System.out.println("index 范围异常");
                return null;
            }
            Node<T> n = getNode(index);
            // 获取删除元素的上一个元素
            Node<T> preNode = n.getPreNode();
            preNode.setNextNode(n.getNextNode());
            n.getNextNode().setPreNode(preNode);
            n.setPreNode(null);
            n.setNextNode(null);
            size--;
            return n.getItem();
        }
    
        @Override
        public void add(T elem) {
            Node<T> newNode = new Node<T>(elem);
            // 获取指定位置的前一个节点
            Node<T> preNode = last.getPreNode();
            preNode.getNextNode().setPreNode(newNode);
            newNode.setNextNode(preNode.getNextNode());
            preNode.setNextNode(newNode);
            newNode.setPreNode(preNode);
            size++;
        }
    
        @Override
        public T pop() {
    
            return remove(size);
        }
    
        @Override
        public void removeAll() {
            while (size > 0) {
                pop();
            }
        }
    
    }
    
    /** * * @ClassName: Node * @Description:双向链表节点 * @author xiaomu * @date 2018年1月15日 上午11:44:12 * * @param <T> */
    class Node<T> {
        protected Node<T> nextNode;
        protected T item;
        protected Node<T> preNode;
    
        public Node<T> getNextNode() {
            return nextNode;
        }
    
        public void setNextNode(Node<T> nextNode) {
            this.nextNode = nextNode;
        }
    
        public T getItem() {
            return item;
        }
    
        public void setItem(T item) {
            this.item = item;
        }
    
        public Node<T> getPreNode() {
            return preNode;
        }
    
        public void setPreNode(Node<T> preNode) {
            this.preNode = preNode;
        }
    
        public Node(T item) {
            this.nextNode = null;
            this.item = item;
            this.preNode = null;
        }
    
        public Node() {
            this(null);
        }
    
    }