Java集合框架LinkedList详解及实例_Java教程

Java集合框架LinkedList详解及实例

2020-09-08 10:39Java之家 Java教程

这篇文章主要介绍了Java集合框架LinkedList详解及实例的相关资料,从定义，概述，用法进行介绍，需要的朋友可以参考下

Java集合框架LinkedList详解

LinkedList定义

									package java.util;

									public class LinkedList<E>

									 extends AbstractSequentialList<E>

									 implements List<E>, Deque<E>, Cloneable, java.io.Serializable{

									 transient int size = 0;

									 transient Node<E> first;

									 transient Node<E> last;

									}

LinkedList概述

LinkedList以双向链表实现，允许重复。（如下Node的实现）并保留头指针和尾指针。

									private static class Node<E> {

									 E item;

									 Node<E> next;

									 Node<E> prev;

									 Node(Node<E> prev, E element, Node<E> next) {

									  this.item = element;

									  this.next = next;

									  this.prev = prev;

									 }

									}

链表无容量限制，但双向链表本身使用了更多空间，也需要额外的链表指针操作。

按下标访问元素—get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半，会从末尾移起)。

									public E get(int index) {

									 checkElementIndex(index);

									 return node(index).item;

									}

									public E set(int index, E element) {

									 checkElementIndex(index);

									 Node<E> x = node(index);

									 E oldVal = x.item;

									 x.item = element;

									 return oldVal;

									}

									Node<E> node(int index) {

									 // assert isElementIndex(index);

									 if (index < (size >> 1)) {

									  Node<E> x = first;

									  for (int i = 0; i < index; i++)

									   x = x.next;

									  return x;

									 } else {

									  Node<E> x = last;

									  for (int i = size - 1; i > index; i--)

									   x = x.prev;

									  return x;

									 }

									}

插入、删除元素时修改前后节点的指针即可，但还是要遍历部分链表的指针才能移动到下标所指的位置，只有在链表两头的操作—add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指针的移动。

非线程安全，可以调用Collections.synchronizedList(new LinkedList<>());实现。

LinkedList用法

简单举个例子：

									List<Integer> list = new LinkedList<>();

									list.add(4);

									list.add(2);

									list.add(3);

									list.add(5);

									for(int i:list)

									 System.out.println(i);

									System.out.println(list);

运行结果：

									4

									2

									3

									5

									[4, 2, 3, 5]

LinkedList会保留插入数据的顺序。

subList的使用

									List<Integer> list = new LinkedList<>();

									 list.add(4);

									 list.add(2);

									 list.add(3);

									 list.add(5);

									 list.add(7);

									 list.add(5);

									 list.add(11);

									 list.add(14);

									 list.add(10);

									 list.add(9);

									 System.out.println(list);

									 List<Integer> list2 = list.subList(3, 6);

									 System.out.println(list2);

									 list2.set(2, 50);

									 System.out.println("============");

									 System.out.println(list);

									 System.out.println(list2);

运行结果：

									[4, 2, 3, 5, 7, 5, 11, 14, 10, 9]

									[5, 7, 5]

									============

									[4, 2, 3, 5, 7, 50, 11, 14, 10, 9]

									[5, 7, 50]