文章目录
一、什么是LinkedList？
LinkedList的底层是
双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，LinkedList也实现了List接口，具体如下：
1. LinkedList实现了
List接口
2. LinkedList的底层使用了
双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList
不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
二、LinkedList的使用
构造方法：
| 方法 |
解释 |
|
LinkedList()
|
无参构造
|
|
public LinkedList(Collection<? extends E> c)
|
使用其他集合容器中元素构造List
|
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}
LinkedList的常用方法：
| 方法 |
解释 |
|
boolean add(E e)
|
尾插 e
|
|
void add(int index, E element)
|
将 e 插入到 index 位置
|
|
boolean addAll(Collection<? extends E> c)
|
尾插 c 中的元素
|
|
E remove(int index)
|
删除 index 位置元素
|
|
boolean remove(Object o)
|
删除遇到的第一个 o
|
|
E get(int index)
|
获取下标 index 位置元素
|
|
E set(int index, E element)
|
将下标 index 位置元素设置为 element
|
|
void clear()
|
清空
|
|
boolean contains(Object o)
|
判断 o 是否在线性表中
|
|
int indexOf(Object o)
|
返回第一个 o 所在下标
|
|
int lastIndexOf(Object o)
|
返回最后一个 o 的下标
|
|
List<E> subList(int fromIndex, int toIndex)
|
截取部分 list
|
LinkedList的遍历：(foreach遍历、使用迭代器遍历---正向遍历、使用反向迭代器---反向遍历
LinkedList<String> list = new LinkedList<>();
list.add("javaSE");
list.add("javaWeb");
list.add("javaEE");
// foreach遍历
for (String x: list) {
System.out.print(x + " ");
}
// 使用迭代器遍历---正向遍历
ListIterator<String> list1 = list.listIterator();
while (list1.hasNext()){
System.out.print(list1.next()+" ");
}
// 使用反向迭代器---反向遍历
ListIterator<String> lis2 = list.listIterator(list.size());
while (lis2.hasPrevious()){
System.out.print(lis2.previous()+" ");
}
三、LinkedList自实现
public class MyLinkedList {
static class ListNode{
int val;
ListNode pre;
ListNode next;
public ListNode(int val){
this.val = val;
}
}
public ListNode head;//头部
public ListNode tail;//尾部
public void addFirst(int data){
ListNode node = new ListNode(data);
if (head == null){
head = node;
tail = node;
return;
}
node.next = head;
head.pre = node;
head = node;
}
public void addLast(int data){
ListNode node = new ListNode(data);
if (head == null){
head = node;
tail = node;
return;
}
tail.next = node;
node.pre = tail;
tail = node;
}
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data){
if (index < 0 || index > size()){
System.out.println("index位置不合法！");
return false;
}
if (index == 0){
addFirst(data);
return true;
}
if (index == size()){
addLast(data);
return true;
}
ListNode indexNode = findNode(index);
ListNode node = new ListNode(data);
node.pre = indexNode.pre;
indexNode.pre.next = node;
node.next = indexNode;
indexNode.pre = node;
return true;
}
public ListNode findNode(int index){
ListNode cur = head;
while (index != 0){
cur = cur.next;
index--;
}
return cur;
}
public boolean contains(int key){
ListNode cur = head;
while (cur != null){
if (cur.val == key)return true;
cur = cur.next;
}
return false;
}
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {
head = head.next;
if (head != null) {
head.pre = null;
} else {
tail = null;
}
} else {
cur.pre.next = cur.next;
if (cur.next != null) {
cur.next.pre = cur.pre;
} else {
tail = tail.pre;
}
}
return;
}
cur = cur.next;
}
}
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {
head = head.next;
if (head != null) {
head.pre = null;
} else {
tail = null;
}
} else {
cur.pre.next = cur.next;
if (cur.next != null) {
cur.next.pre = cur.pre;
} else {
tail = tail.pre;
}
}
}
cur = cur.next;
}
}
public int size(){
ListNode cur = head;
int count = 0;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}
public void display(){
ListNode cur = head;
while (cur != null){
System.out.print(cur.val + " ");
cur = cur.next;
}
}
public void clear(){
ListNode cur = head;
while (cur != null){
ListNode temp = cur.next;
cur.next = null;
cur.pre = null;
cur = temp;
}
head = null;
tail = null;
}
}
四、链表实现逆序打印的两种方式（递归和非递归）
递归逆序打印：
public void display(ListNode head) {
if(head == null) {
return;
}
if(head.next == null) {
System.out.print(head.val+" ");
return;
}
display(head.next);
System.out.print(head.val+" ");
}
非递归逆序打印（用栈实现）：
public void display(ListNode head) {
if (head == null) {
return;
}
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
while (!stack.empty()) {
ListNode ret = stack.pop();
System.out.print(ret.val+" ");
}
}
五、ArrayList和LinkedList有什么区别？
ArrayList实质是顺序表，底层是一个数组。LinkedList实质是一个链表。
他们都具有增删查改的功能，但是在实现方式上有区别。比如在插入元素的时候，ArrayList往0位置上插入一个元素，就需把整个数组整体往后移动，时间复杂度为O(N)。而LinkedList只需要修改指向就可以了，时间复杂度为O(1)。但是ArrayList可以支持随机访问，时间复杂度为O(1)，所以一般情况下ArrayList顺序表适合频繁根据下标位置访问，LinkedList比较适合插入和删除比较频繁的情况。
从存储上来说，ArrayList顺序表在物理上和逻辑上都是连续的，但是在扩容的时候，可能会造成空间的浪费。而LinkedList在物理上不一定是连续的，在逻辑上是连续的，可以做到随用随取。
| 不同点 |
ArrayList |
LinkedList |
|
存储空间上
|
物理上逻辑上一定连续
|
逻辑上连续，但物理上不一定连续
|
|
随机访问
|
支持O(1)
|
不支持：O(N)
|
|
头插
|
需要搬移元素，效率低O(N)
|
只需修改引用的指向，时间复杂度为O(1)
|
|
插入
|
空间不够时需要扩容
|
没有容量的概念
|
|
应用场景
|
元素高效存储+频繁访问
|
任意位置插入和删除频繁
|
