java数据结构之链表LinkedList的使用与实现原理解读

一、LinkedList的优缺点 

  • 优点:
    • 插入和删除操作较快,只需要修改对应的指针即可
  • 缺点:
    • 通过索引查找元素较慢

二、LinkedList与其他数据结构的关系

1.LinkedList与集合等结构的关系

LinkedList与其他集合的关系

2.LinkedList实现的方法

LinkedList实现的接口方法

三、LinkedList的使用及实现原理解读

1.LinkedList的属性
  • size : 元素个数
  • first : 链首,链表的第一个节点(Node)
  • last : 链尾,链表的最后一个节点

链表是由各个节点组成的,下面说探讨一下Node节点的结构(LinkedList实际是一个双向链表)

  • item : 元素值
  • next : 当前节点的下一个节点
  • prev : 当前节点的上一个节点
  1. private static class Node<E> {
  2. //节点元素(一般是节点元素的值)
  3. E item;
  4. //节点的下一个元素指针
  5. Node<E> next;
  6. //节点的上一个元素指针
  7. Node<E> prev;
  8.    //在初始化节点时,需要指定元素的值和元素的上下节点 
  9. Node(Node<E> prev, E element, Node<E> next) {
  10. this.item = element;
  11. this.next = next;
  12. this.prev = prev;
  13. }
  14. }
2.LinkedList实例化方法
(1) 链表实例化方法的使用
  • new LinkedList() : 初始化一个空链表
  • new LinkedList(Collection c) :通过一个集合来初始化一个链表,将集合的元素转化为链表节点
  1. //1.无参实例化
  2. List<Integer> linkedList = new LinkedList<Integer>();
  3. linkedList.add(5);
  4. linkedList.add(8);
  5. System.out.println(linkedList); //[5, 8]
  6. //2.通过一个集合来实例化
  7. List<String> courseList = new ArrayList<String>(5);
  8. courseList.add("JAVA编程");
  9. courseList.add("网络安全");
  10. courseList.add("计算机网络");
  11. List<String> examinationList = new LinkedList<String>(courseList);
  12. System.out.println(examinationList); //[JAVA编程, 网络安全, 计算机网络]
(2)链表实例化方法的实现解读
  1. public LinkedList(Collection<? extends E> c) {
  2. //1.调用无参实例化方法
  3. this();
  4. //2.通过addAll方法将集合元素转化为链表节点元素(addAll方法实现在后面讲解)
  5. addAll(c);
  6. }
3.实现迭代器的方法iterator
(1)iterator的使用
  1. List<String> courseList = new ArrayList<String>(5);
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. //直接引用迭代器,通过iterator方法将返回一个Iterator对象
  6. Iterator<String> iterator = courseList.iterator();
  7. while (iterator.hasNext()) {
  8. //通过调用next方法不仅可以返回迭代器下一个元素指向的元素,而且还会将迭代器指针向下移动
  9. System.out.println(iterator.next()); //依次输出:JAVA编程 网络安全 计算机网络
  10. }
(2)iterator的实现解读
  1. public Iterator<E> iterator() {
  2. //通过listIterator()来实现的
  3. return listIterator();
  4. }

实际实现listIterator方法的是ListItr类

  1. private class ListItr implements ListIterator<E> {
  2. //上次返回的节点
  3. private Node<E> lastReturned;
  4. //下次迭代的节点
  5. private Node<E> next;
  6. //下次迭代的节点索引
  7. private int nextIndex;
  8. //期望的修改次数
  9. private int expectedModCount = modCount;
  10. //实例化迭代器,需要指定一个索引值(一般是传入0,从第一个元素开始)
  11. ListItr(int index) {
  12. // 判断当前索引是否为链表的长度,如果等于链表的长度,表示是第后一个节点,那么它的下一个节点就是null
  13. //如果索引值不为链表长度,那么通过node方法来获取节点(遍历链表来获取节点)
  14. /* ------------------------------------------
  15. //通过索引来获取节点元素
  16. Node<E> node(int index) {
  17. //size >> 1是一个右移运算,相当于size / 2 ,即链表的中间位置
  18. //如果索引值比中间位置小,即在链表中间的左边,那么就从开始位置查找
  19. if (index < (size >> 1)) {
  20. //从链表的开头位置开始遍历
  21. Node<E> x = first;
  22. //查找到index的前一个节点,它那它前一个节点的next指向的节点即为index的位置所在节点
  23. for (int i = 0; i < index; i++)
  24. x = x.next;
  25. return x;
  26. } else {
  27. //如果索引值比中间位置小,那么索引值在链表中间位置的右边,那么从链表的结束位置开始查找
  28. Node<E> x = last;
  29. //从结束的位置查找,找到索引值的后一个节点,那么这个节点的前一个指针指向的节点即为index所在的节点
  30. for (int i = size - 1; i > index; i--)
  31. x = x.prev;
  32. return x;
  33. }
  34. }
  35. ---------------------------------------------------*/
  36. next = (index == size) ? null : node(index);
  37. //下一个迭代的索引等于指定的索引值
  38. nextIndex = index;
  39. }
  40. public boolean hasNext() {
  41. //判断下一个迭代的索引值是否小于链表长度,如果大于等于链表长度,就是链表结尾,就没有下一个元素了
  42. return nextIndex < size;
  43. }
  44. public E next() {
  45.    //检查修改次数 
  46. checkForComodification();
  47. //检查是否有下一个节点
  48. if (!hasNext())
  49. throw new NoSuchElementException();
  50.        //上一次返回节点为下一个节点(因为调用next后就返回了当前next节点)
  51. lastReturned = next;
  52. //下一个节点指向下一个节点的下个节点(因为调用next后当前节点就指向了next节点)
  53. next = next.next;
  54. //指向下一个节点的索引值增加
  55. nextIndex++;
  56. //返回上次返回的节点数据
  57. return lastReturned.item;
  58. }
  59. public void remove() {
  60. checkForComodification();
  61. if (lastReturned == null)
  62. throw new IllegalStateException();
  63. //获取上次返回的节点
  64. Node<E> lastNext = lastReturned.next;
  65. //删除上次返回的节点(删除节点即为删除节点的数据,修改其前一个节点的和后一个节点的指向)
  66. /*----------------------------------------------------
  67. //删除节点的方法说明
  68. E unlink(Node<E> x) {
  69. //要删除的节点元素
  70. final E element = x.item;
  71. //要删除的节点的下一个节点
  72. final Node<E> next = x.next;
  73. //要删除的节点的上一个节点
  74. final Node<E> prev = x.prev;
  75. //1.如果它一个节点为null,那么删除的元素就是表头
  76. if (prev == null) {
  77. //因为要删除表头,所以要将表头设置为删除元素的下一个元素
  78. first = next;
  79. } else {
  80. //删除的元素不是表头,就将它前一个元素的next指针指向删除元素的下一个节点
  81. prev.next = next;
  82. //并且将要删除的元素的prev指针指向null
  83. x.prev = null;
  84. }
  85. //2.如果删除元素的下一个节点为null,那么删除的元素就是表尾
  86. if (next == null) {
  87. //如果要删除表尾,那么要将表尾设置为删除元素的上一个元素节点
  88. last = prev;
  89. } else {
  90. //如果要删除的不是表尾,那么就要将删除元素的下一个节点的prev指针指向删除元素的上一个元素节点
  91. next.prev = prev;
  92. //将删除元素的next指针指向null
  93. x.next = null;
  94. }
  95. //删除元素节点为null,以便回收空间
  96. x.item = null;
  97. //减少元素个数
  98. size--;
  99. modCount++;
  100. return element;
  101. }
  102. --------------------------------------------------------*/
  103. unlink(lastReturned);
  104. if (next == lastReturned)
  105. next = lastNext;
  106. else
  107. nextIndex--;
  108. lastReturned = null;
  109. expectedModCount++;
  110. }
  111. //其他方法不再赘述,只说明最基本的迭代器方法
  112. }
4.LinkedList实现Collection接口
(1)contains方法

I.contains方法的使用

  • 作用:检测链表是否包含某个元素
  • 返回值:true|false
  1. List<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. System.out.println(courseList.contains("JAVA编程")); //true

II.contains方法的实现解读

  1. public boolean contains(Object o) {
  2. //通过indexOf方法来判断,indexOf是用来判断某个元素在链表中的索引位置,如果没有该元素,则返回 -1
  3. return indexOf(o) != -1;
  4. }
(2)size方法

I.size方法的使用

  • 作用:返回链表的元素个数
  • 返回值:返回链接元素个数的整数
  1. List<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. System.out.println(courseList.size()); //3

II.size方法的实现解读

  1. public int size() {
  2. //size属性值一直记录着元素的个数
  3. return size;
  4. }
(3)isEmpty方法

I.isEmpty方法的使用

  • 作用:判断当前链表是否为空链表

II.isEmpty方法的实现解读

通过size属性是否为0来判断链表是否为空

  1. public boolean isEmpty() {
  2. return size() == 0;
  3. }
(4)实现toArray方法

I.toArray方法使用

  1. List<String> courseList = new ArrayList<String>(5);
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. String[] courseArr = new String[courseList.size()];
  6. courseList.toArray(courseArr);
  7. for (int i = 0; i< courseArr.length; i++) {
  8. System.out.println(courseArr[i]); //依次输出:JAVA编程  网络安全 计算机网络
  9. }

II.toArray方法实现解读

  1. public <T> T[] toArray(T[] a) {
  2. //如果数组长度太短,无法容纳链表的内容,则申请一个新的数组空间,将它a指向一个新的数组空间
  3. if (a.length < size)
  4. //通过反射机制来实现数组的扩容
  5. a = (T[])java.lang.reflect.Array.newInstance(
  6. a.getClass().getComponentType(), size);
  7. int i = 0;
  8. Object[] result = a;
  9. //遍历链表,将链表的节点赋值给数组相应的元素
  10. for (Node<E> x = first; x != null; x = x.next)
  11. result[i++] = x.item;
  12. //如果数组长度大于链表的长度(如果原数组是有值的,而且长度大于链表长度),则将数组第size位设置为null
  13. if (a.length > size)
  14. a[size] = null;
  15. return a;
  16. }
(5)实现add方法

I.add方法的使用

  • 作用:向链表添加或插入节点
  • 使用方式:
    • add(E element) : 在链表结尾添加节点
    • add(int index, E element) :在指定位置添加节点
  1. List<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. courseList.add(2, "计算机组成原理");
  6. System.out.println(courseList);//[JAVA编程, 网络安全, 计算机组成原理, 计算机网络]

II.add方法的实现解读

  1. //在链表结尾添加节点
  2. public boolean add(E e) {
  3. //调用linkLast方法
  4. linkLast(e);
  5. return true;
  6. }
  7. //在指定位置添加节点
  8. public void add(int index, E element) {
  9. checkPositionIndex(index);
  10. //如果要插入的索引位置在链表结尾,则在链表结尾添加
  11. if (index == size)
  12. /*-------------------------------------------------------
  13. void linkLast(E e) {
  14. //1.获取最后一个元素节点
  15. final Node<E> l = last;
  16. //2.生成一个新的节点,它的上一个节点为当前链表结尾节点,下一个节点为null
  17. final Node<E> newNode = new Node<>(l, e, null);
  18. //3.将新节点作为新的链表结尾节点
  19. last = newNode;
  20. //4.如果原结尾节点为null,即原链表是空链表时
  21. if (l == null)
  22.    //空链表时,指定新节点为首节点
  23. first = newNode;
  24. else
  25. //不为空链表时,将原尾节点的下一个元素指针指向新节点
  26. l.next = newNode;
  27. //5.增加链表元素个数
  28. size++;
  29. modCount++;
  30. }
  31. -------------------------------------------------------*/
  32. linkLast(element);
  33. else
  34. //在某个指定位置添加
  35. /*----------------------------------------------
  36. void linkBefore(E e, Node<E> succ) {
  37. //1.获取在插入的位置原节点的前一个节点
  38. final Node<E> pred = succ.prev;
  39. //2.生成新节点,它存储的元素为e,前一个节点指向插入位置的前一个节点,下一个节点指向原插入位置的节点
  40. final Node<E> newNode = new Node<>(pred, e, succ);
  41. //3.将原插入位置的节点的prev指针指向新插入的元素节点
  42. succ.prev = newNode;
  43. //4.如果原插入位置的前一个节点为null,则原链表为空链表时,指定链表首节点为新插入的节点
  44. if (pred == null)
  45. first = newNode;
  46. else
  47. //如果原链表不为空链表时,则将原插入位置的前一个节点的next指针指向新插入的节点
  48. pred.next = newNode;
  49. //5.增加链表元素个数
  50. size++;
  51. modCount++;
  52. }
  53. -----------------------------------------------*/
  54. linkBefore(element, node(index));
  55. }
(6)实现remove方法

I.remove方法的使用

  • remove(Object o) :通过指定删除的对象来删除
  • remove(int index):通过指定索引来删除
  1. List<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. courseList.add("计算机组成原理");
  6. courseList.add("C语言编程");
  7. courseList.remove("网络安全");
  8. System.out.println(courseList); //[JAVA编程, 计算机网络, C语言编程]
  9. courseList.remove(2);
  10. System.out.println(courseList);//[JAVA编程, 网络安全, 计算机组成原理, 计算机网络]

II.remove方法的实现解读

  1. //通过节点对象来删除链表节点
  2. public boolean remove(Object o) {
  3. //如果删除的元素为null
  4. if (o == null) {
  5. //从链首开始遍历,依次查找第一个为null的节点,删除它,并返回
  6. for (Node<E> x = first; x != null; x = x.next) {
  7. if (x.item == null) {
  8. unlink(x);
  9. return true;
  10. }
  11. }
  12. } else {
  13. for (Node<E> x = first; x != null; x = x.next) {
  14. if (o.equals(x.item)) {
  15. /*-------------------------------------------------
  16. //删除节点的方法说明
  17. E unlink(Node<E> x) {
  18. //要删除的节点元素
  19. final E element = x.item;
  20. //要删除的节点的下一个节点
  21. final Node<E> next = x.next;
  22. //要删除的节点的上一个节点
  23. final Node<E> prev = x.prev;
  24. //1.如果它一个节点为null,那么删除的元素就是表头
  25. if (prev == null) {
  26. //因为要删除表头,所以要将表头设置为删除元素的下一个元素
  27. first = next;
  28. } else {
  29. //删除的元素不是表头,就将它前一个元素的next指针指向删除元素的下一个节点
  30. prev.next = next;
  31. //并且将要删除的元素的prev指针指向null
  32. x.prev = null;
  33. }
  34. //2.如果删除元素的下一个节点为null,那么删除的元素就是表尾
  35. if (next == null) {
  36. //如果要删除表尾,那么要将表尾设置为删除元素的上一个元素节点
  37. last = prev;
  38. } else {
  39. //如果要删除的不是表尾,那么就要将删除元素的下一个节点的prev指针指向删除元素的上一个元素节点
  40. next.prev = prev;
  41. //将删除元素的next指针指向null
  42. x.next = null;
  43. }
  44. //删除元素节点为null,以便回收空间
  45. x.item = null;
  46. //减少元素个数
  47. size--;
  48. modCount++;
  49. return element;
  50. }
  51. ---------------------------------------------------*/
  52. unlink(x);
  53. return true;
  54. }
  55. }
  56. }
  57. return false;
  58. }
  59. //通过索引删除节点
  60. public E remove(int index) {
  61. checkElementIndex(index);
  62.    /*------------------------------------------------------------
  63. //通过索引找到节点对象
  64. Node<E> node(int index) {
  65. //size >> 1右移运算相当于size / 2
  66. //1.如果索引值在链表的中间位置的左侧,那么就从链头开始查找
  67. if (index < (size >> 1)) {
  68. //2.起始位置即为链首
  69. Node<E> x = first;
  70. //3.遍历链表,最后个元素就是查找索引的前一个元素,那么它的next指针指向的就是索引指向的节点
  71. for (int i = 0; i < index; i++)
  72. x = x.next;
  73. return x;
  74. } else {
  75. //1.如果索引值在中间位置的右侧,从链尾开始查找
  76. //2.起始位置就是链尾
  77. Node<E> x = last;
  78. //3.遍历链表,最后一个元素就是查找索引位置的后一个元素,那的它的prev指针指向的就是索引指向的节点
  79. for (int i = size - 1; i > index; i--)
  80. x = x.prev;
  81. return x;
  82. }
  83. }
  84. */ 
  85. //1.先通过索引找到要删除的节点对象(node方法)
  86. //2.再调用unlink删除节点
  87. return unlink(node(index));
  88. }
(7)实现addAll方法

I.addAll方法的使用

  • addAll(Collection c):在链表末尾添加节点
  • addAll(int index, Collection c) : 在指定位置批量插入节点
  1. List<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. courseList.add("计算机组成原理");
  6. courseList.add("C语言编程");
  7. List<String> courseArrList = new ArrayList<String>(2);
  8. courseArrList.add("计算机英语");
  9. courseArrList.add("高等数学");
  10. courseList.addAll(courseArrList);
  11. System.out.println(courseList); //[JAVA编程, 网络安全, 计算机网络, 计算机组成原理, C语言编程, 计算机英语, 高等数学]
  12. Set<String> courseSet = new HashSet<String>(3);
  13. courseSet.add("线性代数");
  14. courseSet.add("微积分");
  15. courseList.addAll(5, courseSet);
  16. System.out.println(courseList); //[JAVA编程, 网络安全, 计算机网络, 计算机组成原理, C语言编程, 线性代数, 微积分, 计算机英语, 高等数学]

II.addAll方法的实现解读

  1. //不指定位置时,默认在链表结束添加元素
  2. public boolean addAll(Collection<? extends E> c) {
  3. //调用在指定位置批量添加元素的方法
  4. return addAll(size, c);
  5. }
  6. //在指定位置批量添加节点
  7. public boolean addAll(int index, Collection<? extends E> c) {
  8. //检查索引值的合法性
  9. checkPositionIndex(index);
  10. //1.将插入的集合元素转化为数组a
  11. Object[] a = c.toArray();
  12. //2.获取数组的长度即插入节点的个数
  13. int numNew = a.length;
  14. //3.如果插入的节点个数为0,直接返回
  15. if (numNew == 0)
  16. return false;
  17. //pred用来表示插入元素的prev指针节点,succ表示插入索引的原位置节点
  18. Node<E> pred, succ;
  19. //4.如果插入的索引位置和链表个数相等,即在链表结尾添加节点
  20. if (index == size) {
  21. //5.如果插入的位置是链表结尾,那么插入位置的原节点是null
  22. succ = null;
  23. //6.而且链表插入位置的prev指针就是原链表最后一个节点
  24. pred = last;
  25. } else {
  26. //如果插入位置不是链表结尾,那么根据index值查找到原插入位置的节点
  27. succ = node(index);
  28. //插入位置的节点的prev指针就是原插入节点的prev指针
  29. pred = succ.prev;
  30. }
  31. //7.遍历插入的新节点
  32. for (Object o : a) {
  33. //8.生成新节点,它对应的元素为e,它的prev指针为pred,next指针为null
  34. E e = (E) o;
  35. Node<E> newNode = new Node<>(pred, e, null);
  36. //9.如果prev指针是null则表示原链表是一个空链表,那么将链表的first指针指向插入的节点
  37. if (pred == null)
  38. first = newNode;
  39. else
  40. //10.如果原链表不是空链表,那么插入位置的next指针就是当前插入的节点
  41. pred.next = newNode;
  42. pred = newNode;
  43. }
  44. //11.如果插入的位置是原链表结尾
  45. if (succ == null) {
  46. //那么last指针指向插入位置的prev指针
  47. last = pred;
  48. } else {
  49. //12.如果插入位置不在原链表结尾,那么插入位置的前一个元素的next指针,指向插入位置的元素,而插入位置的元素节点的prev指针指向插入位置的前一个节点
  50. pred.next = succ;
  51. succ.prev = pred;
  52. }
  53. //增加链表节点个数
  54. size += numNew;
  55. modCount++;
  56. return true;
  57. }
(8)实现removeAll方法

I.removeAll方法的使用

  • removeAll(Collection c):批量删除指定集合的节点
  1. List<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. courseList.add("高等数学");
  6. courseList.add("概率论与数理统计");
  7. courseList.add("线性代数");
  8. courseList.add("微积分");
  9. Set<String> mathSet = new HashSet<String>();
  10. mathSet.add("高等数学");
  11. mathSet.add("概率论与数理统计");
  12. mathSet.add("线性代数");
  13. mathSet.add("微积分");
  14. courseList.removeAll(mathSet);
  15. System.out.println(courseList); //[JAVA编程, 网络安全, 计算机网络]

II.removeAll方法的实现解读

  1. public boolean removeAll(Collection<?> c) {
  2. Objects.requireNonNull(c);
  3. boolean modified = false;
  4. //1.获取当前链表的迭代器
  5. Iterator<?> it = iterator();
  6. while (it.hasNext()) {
  7. //2.判断删除的集合中是否有当前迭代器中元素
  8. if (c.contains(it.next())) {
  9. //3.调用对应的迭代器对象删除节点
  10. /*--------------------------------------------------------------
  11. //实际调用的是AbstractList中的Itr的remove方法
  12. public void remove() {
  13. if (lastRet < 0)
  14. throw new IllegalStateException();
  15. checkForComodification();
  16. try {
  17. //调用LinkedList的remove方法
  18. AbstractList.this.remove(lastRet);
  19. if (lastRet < cursor)
  20. cursor--;
  21. lastRet = -1;
  22. expectedModCount = modCount;
  23. } catch (IndexOutOfBoundsException e) {
  24. throw new ConcurrentModificationException();
  25. }
  26. }
  27. ---------------------------------------------------------------*/
  28. it.remove();
  29. modified = true;
  30. }
  31. }
  32. return modified;
  33. }
(9)实现clear方法

I.clear方法的使用

  • 作用:清空链表
  1. List<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. courseList.clear();
  6. System.out.println(courseList.isEmpty()); //true

II.clear方法的实现解读

  1. public void clear() {
  2. //1.遍历整个链表,将每个元素存储的元素设置为null,并将它的prev,next指针都指向null
  3. for (Node<E> x = first; x != null; ) {
  4. Node<E> next = x.next;
  5. x.item = null;
  6. x.next = null;
  7. x.prev = null;
  8. x = next;
  9. }
  10. //2.将链表的表头和表尾都设置为null
  11. first = last = null;
  12. //3.将链表元素个数设置为0
  13. size = 0;
  14. modCount++;
  15. }
5.LinkedList实现List接口
(1)set方法

I.set方法的使用

  • set(int index, E value):为指定索引位置设置新的元素对象
  1. List<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. courseList.set(1, "计算机文化基础");
  6. System.out.println(courseList); //[JAVA编程, 计算机文化基础, 计算机网络]

II.set方法的实现解读

  1. public E set(int index, E element) {
  2. checkElementIndex(index);
  3. //1.通过索引获取到对应的原节点对象,node函数之前已经介绍过,在此不再赘述
  4. Node<E> x = node(index);
  5. //2.获取原节点对象的值
  6. E oldVal = x.item;
  7. //3.为当前索引对应的元素设置新的值
  8. x.item = element;
  9. return oldVal;
  10. }
(2)get方法

I.get方法的使用

  • get(int index):获取指定索引位置对应的节点
  1. List<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. String tmp = courseList.get(1);
  6. System.out.println(tmp); //网络安全

II.get方法的实现解读

  1. public E get(int index) {
  2. checkElementIndex(index);
  3. //通过node方法查找到节点,再获取节点的item属性值
  4. return node(index).item;
  5. }
  • List接口其他方法,在些不再赘述,使用方式与ArrayList基本一致,因为它们都实现了List接口,实现原理,基本上都是通过node方法来获取元素
6.LinkedList实现Queue接口
(1)offer方法
  • offer即为在队尾添加元素,是使用add方法实现的,和add(E e)是一样的,在此不再赘述
(2)poll方法

I.poll方法的使用:

  • poll : 弹出队列的第一个元素
  1. LinkedList<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. courseList.add("计算机文化基础");
  6. String first = courseList.poll();
  7. System.out.println(first); //JAVA编程
  8. System.out.println(courseList); //[网络安全, 计算机网络, 计算机文化基础]

II.poll方法的实现解读:

  1. public E poll() {
  2. //1.获取队列的第一个元素
  3. final Node<E> f = first;
  4. //2.如果队列的第一个元素不为null,那么从队列中将它删除掉
  5. /*-------------------------------------------------
  6. //删除第一个元素
  7. private E unlinkFirst(Node<E> f) {
  8. final E element = f.item;
  9. final Node<E> next = f.next;
  10. //1.删除节点本身
  11. f.item = null;
  12. //2.节点的next指针指向null
  13. f.next = null;
  14. //3.将队列的头元素节点指向当前头元素的下一个节点
  15. first = next;
  16. //4.如果旧头节点的next指针是null,也就是原队列就一个元素
  17. if (next == null)
  18. //尾节点为null(本身就一个节点,既是头节点,也是尾节点,删除了,就没了,是个空队列了)
  19. last = null;
  20. else
  21. //还有下一个节点,那么就将原队列的第二个节点的prev指针指向null,第二个节点成为新的头节点
  22. next.prev = null;
  23. //5.减少队列的节点个数
  24. size--;
  25. modCount++;
  26. return element;
  27. }
  28. ---------------------------------------------------*/
  29. return (f == null) ? null : unlinkFirst(f);
  30. }
(3)element方法
  • element方法是获取队列头元素的值,是通过读取first属性来实现的
(4)peek方法
  • peek是从队列中获取队尾元素的值,是通过获取last的属性来实现的
(5)push方法

I.push的使用

  • push:在链表开头插入元素节点
  1. LinkedList<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. courseList.push("计算机文化基础");
  6. System.out.println(courseList); //[计算机文化基础, JAVA编程, 网络安全, 计算机网络]

II.push的实现方式

  1. public void push(E e) {
  2. /*
  3. ---------------------------------------------
  4. public void addFirst(E e) {
  5. linkFirst(e);
  6. }
  7. private void linkFirst(E e) {
  8. //1.获取头节点
  9. final Node<E> f = first;
  10. //2.生成新插入的节点
  11. final Node<E> newNode = new Node<>(null, e, f);
  12. //3.将链表头指向新插入的节点
  13. first = newNode;
  14. //4.如果原链表头是null,即原链表是空链表,那么插入的元素就是唯一的元素节点,链表的尾节点也是新插入的元素节点
  15. if (f == null)
  16. last = newNode;
  17. else
  18. //如果原链表有节点,那么原表头成为第二个节点,它的prev指针指向新节点
  19. f.prev = newNode;
  20. //5.增加链表元素个数
  21. size++;
  22. modCount++;
  23. }
  24. ---------------------------------------------
  25. */
  26. addFirst(e);
  27. }
(6)pop方法

它的功能与poll方法一致,在此不再赘述

7.其他方法的使用及实现
(1)clone方法

I.clone方法的使用:

  1. LinkedList<String> courseList = new LinkedList<String>();
  2. courseList.add("JAVA编程");
  3. courseList.add("网络安全");
  4. courseList.add("计算机网络");
  5. LinkedList<String> cloneCourseList = (LinkedList<String>) courseList.clone();
  6. System.out.println(cloneCourseList); //[JAVA编程, 网络安全, 计算机网络]

II.clone方法实现解读:

  1. public Object clone() {
  2. /*-----------------------------------------------
  3. private LinkedList<E> superClone() {
  4. try {
  5. //调用基类Object对象clone的方法
  6. return (LinkedList<E>) super.clone();
  7. } catch (CloneNotSupportedException e) {
  8. throw new InternalError(e);
  9. }
  10. }
  11. ------------------------------------------------*/
  12. //1.对象克隆
  13. LinkedList<E> clone = superClone();
  14. //2.将克隆对象的链表头和链表尾都指向null,并且节点个数设置为0,即为一个空表
  15. clone.first = clone.last = null;
  16. clone.size = 0;
  17. clone.modCount = 0;
  18. //3.遍历原链表对象的节点,依次添加到新克隆对象上
  19. for (Node<E> x = first; x != null; x = x.next)
  20. clone.add(x.item);
  21. return clone;
  22. }