devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

List接口的具体实现类：LinkedList、Vector_linkedlist元素值可以重复吗

作者：凡人多烦事01 | 2024-03-27 05:11:14

赞

踩

linkedlist元素值可以重复吗

List接口的具体实现类：ArrayList、LinkedList、Vector

LinkedList的使用细节：

        1.LinkedList中可以添加任意元素，包括null

        2.LinkedList中的元素可以重复

        3.LinkedList底层通过双向链表来存取数据

        4.LInkedList中的方法没有使用synchronized修饰，因此只能单线程

LinkedList底层结构：

        1.LinkedList底层维护了双向链表

        2.LinkedList中维护了两个属性first、last，分别指向链表的首、尾节点

        3.LinkedList每一个节点（Node）维护了三个属性prev、next、item

                prev指向前一个节点，next指向后一个节点，item存储数据

因此，LinkedList通过双向链表完成数据的增删改查，而不是数组，相对效率更高。

  1. // 模拟双向链表
  2. Node jack = new Node("jack");
  3. Node tom = new Node("tom");
  4. Node kxg = new Node("kxg");
  5.     // 连接三个节点，形成双向链表
  6.         // Jack -> tom -> kxg
  7. jack.next = tom;
  8. tom.next = kxg;
  9.         // kxg -> tom -> jack
  10. kxg.pre = tom;
  11. tom.pre = jack;
  12.     // 双向链表的头、尾节点
  13. Node first = jack;
  14. Node last = kxg;
  15.     // 从头到尾遍历双向链表
  16. while(true) {
  17.     if (first == null) {
  18.         break;
  19.     }
  20.     System.out.println(first);
  21.     first = first.next;
  22. }
  23. // 从尾到头遍历双向链表
  24. while (true) {
  25.     if (last == null) {
  26.         break;
  27.     }
  28.     System.out.println(last);
  29.     last = last.pre;
  30. }
  31. // 双向链表的添加与删除
  32.     // 在tom与kxg中插入Smith
  33. Node smith = new Node("Smith");
  34.     // 改变链表中的指向
  35. tom.next = smith;
  36. smith.next = kxg;
  37. kxg.pre = smith;
  38. smith.pre = tom;
  39.  
  40. // 定义节点类：每一个Node类的实例对象都对应链表的一个节点
  41. class Node {
  42.     private Object item; // 存储节点数据
  43.     public Node prev; // 指向前一个节点
  44.     public Node next; // 指向下一个节点
  45.  
  46.     // 构造器
  47.     public Node(Object item) {
  48.         this.item = item;
  49.     }
  50. }

LinkedList的增删改查操作：

  1. LinkedList linkedList = new LinkedList();
  2.     // 向链表中追加
  3. linkedList.add(12);
  4. linkedList.add("99");
  5. linkedList.add(25);
  6. linkedList.add("kxg");
  7.     // 向链表中删除
  8.         // remove():默认删除链表中的第一个节点
  9.         // remove(int index)：链表中的指定节点
  10.         // remove(Object o):比较对象，做出删除
  11. linkedList.remove();
  12.     // 修改链表
  13. linkedList.set(1, 100);
  14.     // 得到链表中的某个元素
  15. Object obj = linkedList.get(0);

LinkedList的源码分析：

        1.首先调用无参构造器，创建空链表。此时，first=null、last=null、size=0

public LinkedList() {};

        2.向链表中添加首个元素，调用add方法。此时，first=last=该节点、size=1

  1. public boolean add(E e) {
  2.     linkLast(e);
  3.     return true;
  4. }
  5. // 进入linkLast()方法完成添加操作
  6. void linkLast(E e) {
  7.     // 保存之前链表的尾节点
  8.     final Node<E> l = last;
  9.     // 创建新节点，prev=null；item=e；next=null
  10.     final Node<E> newNode = new Node<>(l, e, null);
  11.     // 改变链表中的last指向
  12.     last = newNode;
  13.     // 将新节点加入链表中
  14.     if (l == null)
  15.         // 首次添加链表为空时，first指向新节点
  16.         first = newNode;
  17.     else
  18.         l.next = newNode;
  19.     // 链表长度+1，修改次数+1
  20.     size++;
  21.     modCount++;
  22.  }

        3.向链表中再次追加元素，调用add方法，改变链表指向

  1. void linkLast(E e) {
  2.     final Node<E> l = last;
  3.     // 创建节点，pre=之前链表的last，item=e，next=null
  4.     final Node<E> newNode = new Node<>(l, e, null);
  5.     // 改变链表中的last指向
  6.     last = newNode;
  7.     // 将新节点加入链表中
  8.     if (l == null)
  9.         first = newNode;
  10.     else
  11.         // 链表不为空时，将新节点加入到链表的最后
  12.         l.next = newNode;
  13.     size++;
  14.     modCount++;
  15. }

        4.删除链表中的元素，调用remove方法

  1. public E remove() {
  2.     return removeFirst();
  3. }
  4. public E removeFirst() {
  5.     final Node<E> f = first;
  6.     // 判断链表是否为空
  7.     if (f == null)
  8.         // 如果链表为空，抛出异常，方法结束
  9.     // 链表不为空，调用unlinkFirst方法
  10.     return unlinkFirst(f);
  11. }
  12. // 进入unlinkFirst方法
  13. private E unlinkFirst(Node<E> f) {
  14.     // assert f == first && f != null;
  15.     // 记录第一个节点中保存的数据和它指向的next节点
  16.     final E element = f.item;
  17.     final Node<E> next = f.next;
  18.     // 将第一个节点的item、next都置为null
  19.     f.item = null;
  20.     f.next = null; // help GC
  21.     // 将链表的first指向第一个节点指向的next
  22.     first = next;
  23.     if (next == null)
  24.         // 链表仅仅只有一个元素，将first和last置为空
  25.         last = null;
  26.     else
  27.         // 将新的第一个节点的prev置为null，断开与原来第一个的连接
  28.         next.prev = null;
  29.     // 长度-1
  30.     size--;
  31.     modCount++;
  32.     return element;
  33. }

List的实现类：Vector

Vector类的使用细节：

        1.Vector使用对象数组进行数据的存取。protected object[] elementData

        2.Vector中的方法通过synchronized修饰，实现了线程同步（线程安全）

Vector的源码分析:

调用无参构造器：

  1. Vector vector1 = new Vector();
  2. for(int i = 0; i < 10; i++) {
  3.     vector1.add(i);
  4. }
  5. vector1.add("kxg");

        1.调用构造器

  1. public Vector() {
  2.     this(10);
  3. }

        2.Vector底层默认调用含参构造器，创建size=10的集合

  1. public Vector(int initialCapacity) {
  2.     this(initialCapacity, 0);
  3. }

        3.将元素加入集合中，判断是否需要扩容

  1. public synchronized boolean add(E e) {
  2.     modCount++;
  3.     ensureCapacityHelper(elementCount + 1);
  4.     // 将元素加入集合中
  5.     elementData[elementCount++] = e;
  6.     return true;
  7. }
  8. private void ensureCapacityHelper(int minCapacity) {
  9.     // overflow-conscious code
  10.     // 根据minCapacity与elementData.length的大小，判断集合是否需要进行扩容
  11.     if (minCapacity - elementData.length > 0)
  12.         grow(minCapacity);
  13. }

        4.对数组进行扩容

  1. private void grow(int minCapacity) {
  2.     // overflow-conscious code
  3.     int oldCapacity = elementData.length;
  4.     // capacityIncrement在双参构造器中，可以指定扩容的大小，默认为0
  5.     // capacityIncrement=0，所以newCapacity=oldCapacity+oldCapacity，扩容两倍
  6.     int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
  7.     if (newCapacity - minCapacity < 0)
  8.         newCapacity = minCapacity;
  9.     // 需要存储的数据过多
  10.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  11.         newCapacity = hugeCapacity(minCapacity);
  12.     // 将数组进行复制存储
  13.     elementData = Arrays.copyOf(elementData, newCapacity);
  14. }

调用含参构造器（一个参数）:

  1. Vector vector2 = new Vector(8);
  2. for (int i = 0; i < 8; i++) {
  3.     vector2.add("hello" + i);
  4. }
  5. vector2.add("kxg");

        1.调用含参构造器，创建指定大小的数组，默认其扩容长度为0

  1. public Vector(int initialCapacity) {
  2.     this(initialCapacity, 0);
  3. }

        2.调用双参构造器

  1. public Vector(int initialCapacity, int capacityIncrement) {
  2.     super();
  3.     // 传入的参数<0，抛出异常
  4.     if (initialCapacity < 0)
  5.         throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
  6.     // 创建指定大小的集合数组
  7.     this.elementData = new Object[initialCapacity];
  8.     // 默认扩容大小为0
  9.     this.capacityIncrement = capacityIncrement;
  10. }

        3.后面与无参构造器操作相同

调用含参构造器（两个参数）：

  1. Vector vector3 = new Vector(4, 4);
  2. for (int i = 0; i < 4; i++) {
  3.     vector3.add("kxg");
  4. }
  5. vector3.add("kxg");

        1.调用含参构造器，传入初始大小、扩容大小

  1. public Vector(int initialCapacity, int capacityIncrement) {
  2.     super();
  3.     if (initialCapacity < 0)
  4.         throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
  5.     this.elementData = new Object[initialCapacity];
  6.     this.capacityIncrement = capacityIncrement;
  7. }

        2.按照指定大小进行扩容

Vector的扩容机制：

        调用无参构造器，默认初始大小为8，之后按照两倍进行扩容

        调用一个参数的构造器，默认初始大小为指定长度，之后按照两倍进行扩容

        调用两个参数的构造器，默认初始大小为指定长度，之后按照指定大小进行扩容

ArrayList、LinkedList、Vector之间的区别与联系：

        ArrayList：可变数组elementData[]

                增加删除效率低，必须通过数组扩容进行处理

                修改查询效率高

        LinkedList：双向链表

                增加删除效率高，仅仅改变链表中的指向

                修改查询效率低

        Vector：可变数组object[]

其中ArrayList、LinkedList都是线程不安全的，效率高；

        Vector线程安全，效率低。

因此，存储数据时，多线程情况下选择Vector；单线程时，若对数据添加删除操作更多，选择LinkedList；若对数据修改查询操作更多，选择ArrayList

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/322022
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号