LinkedList

LinkedList的概述

LinkedList的底层使用双向链表实现。

链表是一种线性数据结构，其中每个元素都是一个单独的对象，包含一个指向列表中下一个节点的引用。

它可以用于实现各种抽象数据类型，例如列表、堆栈、队列等。

LinkedList的优缺点

优点

• 插入和删除操作的时间复杂度为O(1)，相比于数组的O(n)更加高效。
• 链表的大小可以动态调整，不像数组需要预先分配空间。
• 链表的节点可以在内存中部连续存储，因此可以更加的灵活的利用内存空间。

缺点

• 访问元素的时间复杂度为O(n)，相比于数组的O(1)较低效。
• 链表需要额外的空间来存储指向下一个节点的指针，因此占用的空间比数组更大。
• 链表的随机访问效率比较低，因为需要从头开始遍历链表才能找到指定位置的节点。

LinkedList的创建方式

LinkedList linkedList = new LinkedList();
//向上转型
List linkedLists = new LinkedList();

常用方法，以及源码分析

add(E e)

源码分析：

通过调用 linkLast(E e) 方法将元素添加到链表的末尾。

linkLast(E e) 方法创建一个新的节点，并将其插入到链表的末尾。如果链表为空，则将新节点设置为第一个节点。否则，将新节点链接到最后一个节点。最后，更新链表的大小和 modCount 变量。

	public boolean add(E e) {//调用linklast方法将元素添加到链表的尾端linkLast(e);//添加成功，返回truereturn true;}void linkLast(E e) {//获取链表的最后一个节点final Node<E> l = last;//创建最后一个节点，他的前驱节点是l，后去节点为null，数据为efinal Node<E> newNode = new Node<>(l, e, null);//将链表的尾节点指向新节点last = newNode;//判断节点是否为nullif (l == null)//为null则将节点指向新节点first = newNode;else//如果不为null，将原尾节点的后继节点指向新节点l.next = newNode;//聊表的大小加1size++;//修改计数器modCount++;}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();//添加数据linkedList.add("张三");linkedList.add("李四");//输出此列表System.out.println(linkedList);}

add(int index, E element)

源码分析：

将元素添加到指定位置

public void add(int index, E element) {//检查索引是否越界checkPositionIndex(index);//索引与长度相等if (index == size)//在链表尾部添加数据linkLast(element);else//在指定位置之前添数据linkBefore(element, node(index));}private void checkPositionIndex(int index) {//判断索引是否合法if (!isPositionIndex(index))//不合法则抛出下标越界异常throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}void linkLast(E e) {//获取链表的最后一个节点final Node<E> l = last;//创建一个新的节点，他的前驱节点是l，后去节点为null，数据为efinal Node<E> newNode = new Node<>(l, e, null);//将链表的最后一个节点指向新节点last = newNode;//判断链表是否为nullif (l == null)//将第一个节点指向新节点first = newNode;//如果不为nullelse//将最后一个节点的下一个节点指向新节点l.next = newNode;//链表大小加1size++;//修改计数器加1modCount++;}void linkBefore(E e, Node<E> succ) {//获取指定位置的前一个节点final Node<E> pred = succ.prev;//创建一个新节点final Node<E> newNode = new Node<>(pred, e, succ);//将指定位置的前一个节点的下一个节点指向新节点succ.prev = newNode;//如果指定位置的前一个节点为null，if (pred == null)//将第一个节点指向新节点first = newNode;//如果指定位置的前一个节点不为nullelse//将前一个节点的下一个节点指向新节点pred.next = newNode;//链表大小加1size++;//修改计数器加1modCount++;}

案例:

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");System.out.println(linkedList);//位置1，添加数据linkedList.add(1,"王五");System.out.println(linkedList);
}

addFirst(E e)

源码分析：

将指定元素插入到此列表的开头

public void addFirst(E e) {// 在链表的头部添加一个新节点linkFirst(e);
}
private void linkFirst(E e) {// 获取头节点final Node> f = first;// 创建一个新节点，它的前驱节点为null，数据为e，后继节点为头节点ffinal Node> newNode = new Node<>(null, e, f);// 将头节点指向新节点first = newNode;// 如果头节点为null，说明if (f == null)//链表为空，将尾节点指向新节点last = newNode;// 否则将头节点的前驱节点指向新节点elsef.prev = newNode;// 链表长度加1size++;// 修改次数加1modCount++;}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");System.out.println(linkedList);linkedList.add(1,"王五");System.out.println(linkedList);//列表开头添加数据linkedList.addFirst("赵六");System.out.println(linkedList);}

addLast(E e)

源码分析：

将指定元素添加到此列表的结尾

 public void addLast(E e) {//在链表的尾部添加一个新节点linkLast(e);}
void linkLast(E e) {//获取链表的最后一个节点final Node<E> l = last;//创建一个新的节点，他的前驱节点是l，后去节点为null，数据为efinal Node<E> newNode = new Node<>(l, e, null);//将链表的最后一个节点指向新节点last = newNode;//判断链表是否为nullif (l == null)//将第一个节点指向新节点first = newNode;//如果不为nullelse//将最后一个节点的下一个节点指向新节点l.next = newNode;//链表大小加1size++;//修改计数器加1modCount++;}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");System.out.println(linkedList);linkedList.add(1,"王五");System.out.println(linkedList);linkedList.addFirst("赵六");System.out.println(linkedList);//列表结尾添加数据linkedList.addLast("唐七");System.out.println(linkedList);
}

clear()：

源码分析:

从此列表中移除所有元素

public void clear() {// 遍历链表中的每一个节点for (Node<E> x = first; x != null; ) {// 保存当前节点的下一个节点Node<E> next = x.next;// 将当前节点的数据项置为nullx.item = null;// 将当前节点的前驱和后继节点都置为nullx.next = null;x.prev = null;// 将当前节点指向下一个节点x = next;}// 将链表的头节点和尾节点都置为nullfirst = last = null;// 将链表的大小置为0size = 0;// 修改计数器modCount++;
}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");linkedList.add(1,"王五");linkedList.addFirst("赵六");linkedList.addLast("唐七");System.out.println(linkedList);//清除此列表数据linkedList.clear();System.out.println(linkedList);;
}

get(int index)

源码分析：

返回此列表中指定位置处的元素

public E get(int index) {//校验索引是否合法checkElementIndex(index);//返回该索引对应的节点的数据return node(index).item;
}
private void checkPositionIndex(int index) {//判断索引是否合法if (!isPositionIndex(index))//不合法则抛出下标越界异常throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
Node<E> node(int 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;}}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");linkedList.add(1,"王五");linkedList.addFirst("赵六");linkedList.addLast("唐七");System.out.println(linkedList);//获取指定位置的数据System.out.println(linkedList.get(2));
}

getFirst()

源码分析：

返回此列表的第一个元素

public E getFirst() {//获取链表的头节点final Node<E> f = first;//如果头节点为nullif (f == null)//抛出NoSuchElementException异常throw new NoSuchElementException();//返回头节点的数据return f.item;
}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");linkedList.add(1,"王五");linkedList.addFirst("赵六");      linkedList.addLast("唐七");System.out.println(linkedList);//获取此列表的第一个节点System.out.println(linkedList.getFirst());}

remove()

源码分析：

获取并移除此里列表的头（第一个元素）

public E remove() {//调用移除第一个元素方法return removeFirst();
}
public E removeFirst() {// 获取链表的头节点final Node<E> f = first;// 如果头节点为空，if (f == null)//抛出NoSuchElementException异常throw new NoSuchElementException();// 返回调用调用unlinkFirst方法删除头节点并返回删除的元素return unlinkFirst(f);
}private E unlinkFirst(Node<E> f) {// assert f == first && f != null;// 获取头节点的元素final E element = f.item;// 获取头节点的下一个节点final Node<E> next = f.next;// 将头节点的元素置为空f.item = null;// 将头节点的下一个节点置为空，以便垃圾回收f.next = null; // help GC// 将链表的头节点指向原头节点的下一个节点first = next;// 如果原头节点的下一个节点为空if (next == null)//将链表的尾节点也置为空last = null;else// 否则将原头节点的下一个节点的前一个节点置为空next.prev = null;// 链表的大小减1size--;// 修改计数器加1modCount++;// 返回删除的元素return element; 
}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");linkedList.add(1,"王五");linkedList.addFirst("赵六");linkedList.addLast("唐七");//获取并移除此列表的第一个节点System.out.println(linkedList.remove());//输出此列表的全部数据System.out.println(linkedList);
}

remove(int index)

源码分析：

移除指定列表中的指定位置的元素

//删除指定位置的节点
public E remove(int index) {// 检查索引是否越界checkElementIndex(index);// 删除并返回指定位置的节点return unlink(node(index));
}
// 检查索引是否越界
private void checkElementIndex(int index) {// 如果索引越界if (!isElementIndex(index))//则抛出IndexOutOfBoundsException异常throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 删除指定节点
E unlink(Node<E> x) {// 获取节点的值	final E element = x.item;// 获取下一个节点final Node<E> next = x.next;// 获取上一个节点final Node<E> prev = x.prev;// 如果上一个节点为空if (prev == null) {// 将下一个节点设为头节点first = next;} else {// 将上一个节点的下一个节点设为当前节点的下一个节点prev.next = next;// 将当前节点的上一个节点设为空x.prev = null;}// 如果下一个节点为空if (next == null) {// 将上一个节点设为尾节点last = prev;} else {// 将下一个节点的上一个节点设为当前节点的上一个节点next.prev = prev;// 将当前节点的下一个节点设为空x.next = null;}// 将当前节点的值设为空x.item = null;// 链表大小减一size--;// 修改次数加一modCount++;// 返回删除的节点的值return element;
}// 获取指定位置的节点
Node<E> node(int 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;}
}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");linkedList.add(1,"王五");linkedList.addFirst("赵六");linkedList.addLast("唐七");//移除此列表的指定位置的节点System.out.println(linkedList.remove(1));//输出此列表的全部数据System.out.println(linkedList);
}

removeFirst()

源码分析：

移除并返回列表的第一个元素

// 删除链表的头节点
public E removeFirst() {// 获取头节点final Node<E> f = first;// 如果头节点为空，if (f == null)//抛出NoSuchElementException异常throw new NoSuchElementException();// 否则，调用unlinkFirst方法删除头节点return unlinkFirst(f);
}private E unlinkFirst(Node<E> f) {// assert f == first && f != null;// 获取头节点的元素final E element = f.item;// 获取头节点的下一个节点final Node<E> next = f.next;// 将头节点的元素置为空f.item = null;// 将头节点的下一个节点置为空，以便垃圾回收f.next = null; // help GC// 将链表的头节点指向原头节点的下一个节点first = next;// 如果原头节点的下一个节点为空if (next == null)//将链表的尾节点也置为空last = null;else// 否则将原头节点的下一个节点的前一个节点置为空next.prev = null;// 链表的大小减1size--;// 修改计数器加1modCount++;// 返回删除的元素return element; 
}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");linkedList.add(1,"王五");linkedList.addFirst("赵六");linkedList.addLast("唐七");//移除并返回列表的第一个元素System.out.println(linkedList.removeFirst());//输出此列表的全部数据System.out.println(linkedList);
}

removelast()

源码分析：

移除并返回此列表最后一个元素

// 从链表的尾部删除一个节点
public E removeLast() {// 获取尾节点final Node<E> l = last;// 如果尾节点为空if (l == null)//抛出NoSuchElementException异常throw new NoSuchElementException();// 调用unlinkLast方法删除尾节点return unlinkLast(l);
}
// 删除链表中的一个节点
private E unlinkLast(Node<E> l) {// assert l == last && l != null;// 获取节点的数据final E element = l.item;// 获取节点的前一个节点final Node<E> prev = l.prev;// 将节点的数据置为空l.item = null;// 将节点的前一个节点置为空	l.prev = null; // help GC// 将尾节点指向前一个节点last = prev;// 如果前一个节点为空if (prev == null)// 将头节点置为空first = null;else// 将前一个节点的指针置为空prev.next = null;// 链表大小减1size--;// 修改计数器加1modCount++;// 返回被删除节点的数据return element;
}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");linkedList.add(1,"王五");linkedList.addFirst("赵六");linkedList.addLast("唐七");//移除并返回列表的最后一个元素System.out.println(linkedList.removeLast());//输出此列表的全部数据System.out.println(linkedList);
}

set(int index,E element)

源码分析：

将此列表中指定位置的元素替换为指定的元素

public E set(int index, E element) {//检查索引是否越界checkElementIndex(index);// 获取指定索引的节点Node<E> x = node(index);// 获取原节点的值E oldVal = x.item;// 将指定索引的节点的值设置为新值x.item = element;// 返回原节点的值return oldVal;
}private void checkElementIndex(int index) {// 如果索引越界if (!isElementIndex(index))//抛出IndexOutOfBoundsException异常throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}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;}}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");linkedList.addFirst("赵六");linkedList.addLast("唐七");System.out.println("原数据："+linkedList);//指定位置的值替换为指定的元素linkedList.set(2,"小明");System.out.println("修改后的数据："+linkedList);
}

size（）

源码分析：

返回此列表的元素个数

public int size() {//返回链表的长度return size;
}

案例：

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add("张三");linkedList.add("李四");linkedList.addFirst("赵六");linkedList.addLast("唐七");System.out.println(linkedList.size());
}

线程安全

LinkedList不是线程安全的，如果需要在多线程环境下使用LinkedList，需要使用Collections.synchronizedList方法将其包装成线程安全的List

List<String> linkedList = new LinkedList<>();
List<String> synchronizedList = Collections.synchronizedList(linkedList); 

观众老爷看完觉得不错点个赞

咖啡知识