精华内容
参与话题
问答
  • LinkedList

    千次阅读 多人点赞 2018-07-19 16:49:38
    LinkedList也实现了List接口,相对于ArrayList来说,它们的最大区别在于底层数据结构不同,LinkedList的底层是一个双向链表,这也决定了它的最大优点,那就是对于数据的修改比ArrayList更加方便快捷。 相对于...

    LinkedList也实现了List接口,相对于ArrayList来说,它们的最大区别在于底层数据结构不同,LinkedList的底层是一个双向链表,这也决定了它的最大优点,那就是对于数据的修改比ArrayList更加方便快捷。
    相对于ArrayList,LinkedList插入是更快的。因为LinkedList不需要改变数组的大小,也不需要在数组装满的时候要将所有的数据重新装入一个新的数组,类似于插入数据,删除数据时,LinkedList也优于ArrayList,其时间复杂度仅为O(1),而ArrayList删除数据是开销很大的,因为这需要重排数组中的所有数据(除了最后一个元素)。
    下面来看看LinkedList的一些常用方法。



    基本特点:

    1.非同步,线程不安全;
    2.支持null元素,元素可以重复;
    3.可以被当作堆栈、队列或双端队列进行操作。
    4.实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
    5.LinkedList包含两个重要的成员:header 和 size。

    	 ·header是双向链表的表头,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。
    其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该节点所包含的值。 
    	 ·size是双向链表中节点的个数。
    


    常用方法:

    1、add(E e),添加元素,addAll(C c)添加一个集合,返回值都是boolean型。

    		LinkedList<Integer> linkedList = new LinkedList<>();
    		// 默认是尾插
            linkedList.add(10);
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.add(10);
            linkedList.addAll(arrayList);
    

    2.remove(O o),删除元素,参数可选,o值可以为null,返回值是boolean型。

    		// 参数为空时删除头结点
    		linkedList.remove();
    		linkedList.remove(10);
    

    3.get(int index),set(int index, E e),获取与修改,LinkedList体现优点的方法。

    		// 当指定索引超出数据个数时会产生越界异常,返回值是原来索引位置的数据
    		System.out.println(linkedList.set(0,20));
    		// 当指定索引超出数据个数时同样会产生越界异常
    		System.out.println(linkedList.get(10));
    

    4.LinkedList的迭代器

    		Iterator<Integer> integer = linkedList.iterator();
            while(integer.hasNext()){
                System.out.print(integer.next() + " ");
            }
            System.out.println();
    


    使用场景:

    结合LinkedList的优点,可以知道LinkedList适用于对数据进行频繁的修改操作的场景。



    简单实现:

    	class MyLinkedList<T> {
    	    /**
    	     * 结点类
    	     */
    	    class Entry{
            /**
             * 后驱
             */
            private Entry next;
            /**
             * 前驱
             */
            private Entry prev;
            /**
             * 数据
             */
            private T data;
            /**
             * 下标
             */
            private int index;
    
            /**
             * 默认构造方法
             */
            private Entry(){
                this.data = null;
                this.index = -1;
                this.next = null;
                this.prev = null;
            }
    
            /**
             * 带数据的构造方法
             * @param data
             */
            private Entry(T data){
                this.data = data;
                this.index = -1;
                this.next = null;
                this.prev = null;
            }
        }
    
        /**
         * 构造函数
         */
        private Entry head;
        public MyLinkedList(){
            head = new Entry();
        }
    
        /**
         * 添加
         * @param data
         */
        public void add(T data){
            Entry cur = head;
            while (cur.next != null){
                cur = cur.next;
            }
            Entry entry = new Entry(data);
            cur.next = entry;
            entry.prev = cur;
            entry.index = entry.prev.index + 1;
        }
    
        /**
         * 默认删除最后一个结点
         * @return
         */
        public T remove(){
            Entry cur = head;
            while(cur.next != null) {
                cur = cur.next;
            }
            T oldValue = cur.data;
            cur.index = -1;
            cur.data = null;
            cur.prev.next = null;
            return oldValue;
        }
    
        /**
         * 删除指定结点
         * @param data
         */
        public void remove(T data){
            Entry cur = head.next;
            while (cur != null){
                if (cur.data == data){
                    cur.data = null;
                    cur.prev.next = cur.next;
                    while(cur.next != null){
                        cur.next.index--;
                        cur = cur.next;
                    }
                    if (cur.next != null){
                        cur.next.prev = cur.prev;
                    }
                }
                cur = cur.next;
            }
        }
    
        /**
         * get方法
         * @param index
         * @return
         */
        public T get(int index){
            Entry cur = head;
            while(cur.next != null) {
                cur = cur.next;
                if (cur.index == index){
                    return cur.data;
                }
            }
            return null;
        }
    
        /**
         * set方法
         * @param index
         * @param data
         * @return
         */
        public T set(int index, T data){
            Entry cur = head;
            while (cur.next != null){
                cur = cur.next;
                if (cur.index == index){
                    T oldValue = cur.data;
                    cur.data = data;
                    return oldValue;
                }
            }
            return null;
        }
    
        /**
         * 输出
         */
        public void print(){
            Entry cur = head.next;
            while (cur != null){
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    }
    
    展开全文
  • linkedlist

    2017-02-19 13:55:45
    import java.util.LinkedList; /* 2017-02-18 09:57:08 * linkedlist 是list接口的实现类 是一个list 集合 可以根据索引随机访问集合中的元素 * 还实现了deque 接口 可以使用双端队列方法 既可以是栈 也可以是...
    
    
    import java.util.LinkedList;
    
    /* 2017-02-18 09:57:08
     *	linkedlist 是list接口的实现类    是一个list 集合 可以根据索引随机访问集合中的元素
     *	还实现了deque 接口  可以使用双端队列方法   既可以是栈  也可以是队列
     *	内部实现是使用了链表的形式来保存集合中的元素 
     *	随机访问元素的性能较差  插入删除   性能较好      内部只需要改变  指针的地址即可  
     *	vector 也是以数组的形式来存储集合元素 ,实现了线程同步,性能更加不好
     *
     *
     *分析
     ****
     * 都是线性表的两种典型实现
     * arraylist  基于数组的线性表
     * linkedlist 基于链表的线性表   不仅有list 的功能  还实现了deque 的   具有 双端队列、栈的功能
     *
     * queue 队列
     * deque 双端队列   既可以是队列也可是作为栈
     * 
     * 数组是以一块连续的内存区来保存所有的元素  随机访问的性能较好   内部以数组作为底层的实现的集合 在随机访问的性能都较好
     * 内部以链表实现的  插入删除 性能较好   
     * 总体来说  arraylist性能比linkedlist 性能较好
     * 大部分时候都应该是使用arraylist
     * 
     * 
     * 
     * list 集合建议
     *	 遍历list 集合元素        arraylist  vector集合   应该使用 随机访问 方法 get 来遍历   性能更好
     *	 遍历linkedlist  是用迭代器 iterator  来遍历集合
     *
     * 	经常 插入 删除   操作大量数据的list集合的大小 可以使用linkedlist 
     *	arraylist、vector 集合可能需要经常重新分配内存数组的大小 效果不好
     *
     *	多线程需要同时访问list集合的元素时,应该考虑使用collections 集合包装成线性安全的集合
     *
     *
     */
    public class Linkedlistj {
    	public static void main(String[] args) {
    		LinkedList linkedList = new LinkedList();
    		linkedList.add("a");  //list 方法
    		linkedList.offer("b"); //	 deque方法
    		for (int i = 0; i < linkedList.size(); i++) {
    //			Object object = linkedList.get(i);
    //			System.out.println(object);
    			System.out.println(linkedList.get(i));  // list 遍历
    		}
    		
    		System.out.println(linkedList.peekLast());
    	}
    }
    

    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 42,438
精华内容 16,975
关键字:

linkedlist