java实现双向循环链表

快来打我* 2022-09-22 14:58 214阅读 0赞

# 模拟JDK中LinkedList的实现原理进行实现 #

package 链表;
    //java实现循环链表
    public class NewLinkedList<E>{
        
        private int size;
        private Entry<E> header=new Entry(null,null,null);
        //定义节点类型
        private class Entry<E> {
        
              E e;
              Entry<E> after;
              Entry<E> before;
              Entry(E e,Entry before,Entry after){
                this.e=e;
                this.after=after;
                this.before=before;
            }
        }
        //构造方法:
        public NewLinkedList(){
            //刚开始:头的前面是头，头的后面也是头
            header.after=header;
            header.before=header;
        }
        //增加元素
        public void add(E e){
            //每个节点之前的节点永远是头结点之前(也就是尾节点)的节点，
            //后面是头结点(采用尾差法)
            //每次增加一个节点，节点的后面是头，头的前面是节点，
            //节点的前面是头的前面（另外一个节点）,另外一个节点的
            //后面就是我们新加入的节点
            //这样就保证了，我们每次插入的节点都是在末尾，
            Entry<E> node=new Entry<E>(e,header.before,header);
            node.before.after=node;
            node.after.before=node;
            size++;
        }
        //统计链表中元素的个数:
        public int length(){
            return size;
        }
    
    
        //根据索引获取元素
        public E getValue(int index){
    
            Entry<E> node=header.after;
            for(int i=0;i<index;i++){
                node=node.after;
            }
            return node.e;
    
        }
    
        public static void main(String[] args) {
            NewLinkedList<String> list=new NewLinkedList<String>();
            list.add("a");
            list.add("b");
            list.add("c");
            list.add("d");
            list.add("e");
            System.out.println(list.getValue(10));
    
        }
    
    }