双向链表的实现

package com.test.tmp;

public interface IList<E> {

    boolean add(E e);
    
    int getSize();
    
    E get(int index);
    
    E getFirst();
    
    E getLast();
    
    boolean remove(int index);
    
    boolean remove(E e);
    
    boolean contains(E e);
    
    void reverse();
}

 

 

 

实现类

 

 

package com.test.tmp;

import java.util.function.Consumer;


/**
 * 双向链表，非线程安全
 * @author yq
 *
 * @param <E>
 */
public class LinkedList<E> implements IList<E>{

    /**
     * 链表第一个元素
     */
    private Node first;
    
    /**
     * 最后一个元素
     */
    private Node last;
    
    /**
     * 元素个数
     */
    private int size;
    
    /**
     * 双向链表节点结构体，用于构造节点元素 
     */
    private class Node {
        //节点元素值
        E item;
        //节点的前置节点
        Node pre;
        //节点的后直节点
        Node next;
        
        /**
         * 节点构造函数，用于构造节点 
         */
        public Node(Node pre, E item, Node next) {
            this.pre = pre;
            this.item = item;
            this.next = next;
        }
    }
    
    /**
     * 
     */
    @Override
    public boolean add(E e) {
        final Node copyLast = last;
        //加的元素总是在最后，最后的next总是为null
        final Node newNode = new Node(copyLast, e, null);
        //新添加的元素肯定为最后一个元素
        last = newNode;
        /*
         * 如果最后一个元素为null，说明链表为空，添加第一个元素.
         */
        if(copyLast == null) {
            first = newNode;
        } else {
            copyLast.next = newNode;
        }
        //添加一个元素，链表长度加1
        size++;
        return true;
    }

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

    @Override
    public E get(int index) {
        final Node indexNode = indexOf(index);
        return indexNode.item;
    }

    
    
    @Override
    public E getFirst() {
        return first.item;
    }

    @Override
    public E getLast() {
        return last.item;
    }

    /**
     * 根据数组元素下标索引返回对应的元素值
     * @param index 索引号，最小为0，最大为size-1
     */
    @Override
    public boolean remove(int index) {
        if(index < 0) {
            throw new IllegalArgumentException();
        }
        
        if(index == 0) {
            first = first.next;
            first.pre = null;
            size--;
            return true;
        }
        
        if(index == size -1) {
            last = last.pre;
            last.next = null;
            size--;
            return true;
        }
        
        final Node indexNode = indexOf(index);
        final Node indexPre = indexNode.pre;
        final Node indexNext = indexNode.next;
        indexPre.next = indexNext;
        indexNext.pre = indexPre;
        size--;
        return true;
    }

    
    private Node indexOf(int index) {
        Node next = first;
        for(int i = 0 ; i < index; i++) {
            next = next.next;
        }
        return next;
    }
    @Override
    public boolean remove(E e) {
        if(first == null || last == null) {
            return false;
        }
        final Node find = find(e);
        if(find == null) {
            return false;
        }
        
        Node findPre = find.pre;
        Node findNext = find.next;
        if(findNext != null) {
            findPre.next = findNext;
            findNext.pre = findPre;
        } else {
            last = findPre;
            last.next = null;
        }
        
        size--;
        return true;
    }

    private Node find(E e) {
        Node findNode = null;
        Node next = first;
        for(int i = 0 ; i < size ; i++) {
            if(next == null) {
                return next;
            }
            if(next.item != null && next.item.equals(e)) {
                findNode = next;
                break;
            } else if(next.item == null && e == null){
                findNode = next;
                break;
            } 
            next = next.next;
        }
        return findNode;
    }
    @Override
    public boolean contains(E e) {
        boolean founded = false;
        if(size < 1) {
            return false;
        }
        
        Node next = first;
        for(int i = 0 ; i < size; i++) {
            if(next == null) {
                return false;
            }
            if(next.item != null && next.item.equals(e)) {
                founded = true;
                break;
            } else if(next.item == null && e == null){
                founded = true;
                break;
            } 
            next = next.next;
            
        }
        return founded;
    }

    @Override
    public void reverse() {
        first = reverse(first);
    }
    /**
     * 递归反转链表
     * @param first
     * @return
     */
    private Node reverse(Node first) {
        if(first == null) {
            return null;
        }
        if(first.next == null) {
            return first;
        }
        Node second = first.next;
        Node rest = reverse(second);
        second.next = first;
        first.next = null;
        return rest;
    }

    class Iterator implements java.util.Iterator<E> {

        @Override
        public boolean hasNext() {
            return false;
        }

        @Override
        public E next() {
            return null;
        }

        @Override
        public void remove() {
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
        }
        
    }
}