目录
一、链表
由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。
顺序表：物理上了连续，逻辑上连续
链表：物理上不一定连续，逻辑上连续
1.1 链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。链表是由一个一个节点组织起来，整体叫做链表。
实际中链表的结构非常多样，“单向双向”、“带头不带头”、“循环不循环”，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们重点掌握两种:
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 无头双向非循环链表：在Java的集合框架库中LinkedList底层实现就是无头双向非循环链表。
1.2 尝试实现
但是如果直接修改head的话，想再遍历一次就不行了，所以需要使用cur=head，然后使用cur进行遍历。
链表的三个关键点：
- node1.next = node2;
- while(cur!=null)
- cur=cur.next;
头插法：
尾插法：
在任意位置插入：
删除
删除所有：
import java.util.List;
public class MySingleLinkedList {
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//代表链表的头节点
public void createList() {
ListNode node1 = new ListNode(12);
ListNode node2 = new ListNode(23);
ListNode node3 = new ListNode(34);
ListNode node4 = new ListNode(45);
ListNode node5 = new ListNode(56);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
this.head = node1;
}
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
/**
* 从指定位置 newHead 开始打印链表
* @param newHead
*/
public void display(ListNode newHead) {
ListNode cur = newHead;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
public int size(){
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void addFirst(int val) {
ListNode node = new ListNode(val);
node.next = head;
head = node;
}
public void addLast(int val) {
ListNode node = new ListNode(val);
if(head == null) {
head = node;
return;
}
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
public void addIndex(int index,int val) {
//1.判断index的合法性
try {
checkIndex(index);
}catch (IndexNotLegalException e) {
e.printStackTrace();
}
//2.index == 0 || index == size()
if(index == 0) {
addFirst(val);
return;
}
if(index == size()) {
addLast(val);
return;
}
//3. 找到index的前一个位置
ListNode cur = findIndexSubOne(index);
//4. 进行连接
ListNode node = new ListNode(val);
node.next = cur.next;
cur.next = node;
}
private ListNode findIndexSubOne(int index) {
int count = 0;
ListNode cur = head;
while (count != index-1) {
cur = cur.next;
count++;
}
return cur;
}
private void checkIndex(int index) throws IndexNotLegalException{
if(index < 0 || index > size()) {
throw new IndexNotLegalException("index不合法");
}
}
public boolean contains(int val) {
ListNode cur = head;
while (cur != null) {
if(cur.val == val) {
return true;
}
cur = cur.next;
}
return false;
}
public void remove(int val) {
if(head == null) {
return;
}
if(head.val == val) {
head = head.next;
return;
}
ListNode cur = head;
while (cur.next != null) {
if(cur.next.val == val) {
ListNode del = cur.next;
cur.next = del.next;
return;
}
cur = cur.next;
}
}
public void removeAllKey(int val) {
//1. 判空
if(this.head == null) {
return;
}
//2. 定义prev 和 cur
ListNode prev = head;
ListNode cur = head.next;
//3.开始判断并且删除
while(cur != null) {
if(cur.val == val) {
prev.next = cur.next;
//cur = cur.next;
}else {
prev = cur;//prev = prev.next;
//cur = cur.next;
}
cur = cur.next;
}
//4.处理头节点
if(head.val == val) {
head = head.next;
}
}
public void clear() {
//head = null;
ListNode cur = head;
while (cur != null) {
ListNode curN = cur.next;
//cur.val = null;
cur.next = null;
cur = curN;
}
head = null;
}
public ListNode reverseList() {
if(head == null) {
return head;
}
ListNode cur = head.next;
head.next = null;
while(cur != null) {
ListNode curN = cur.next;
//开始翻转
cur.next = head;
head = cur;
cur = curN;
}
return head;
}
public ListNode middleNode() {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
//k 不确定是否有效
public int kthToLast( int k) {
if(k <= 0 || head == null) {
return -1;
}
ListNode fast = head;
ListNode slow = head;
//1.先让fast走K-1步
int count = 0;
while(count != k-1) {
fast = fast.next;
if(fast == null) {
return -1;
}
count++;
}
//2、然后一起走，当fast走到最后一个节点的时候 slow的位置就是倒数第K个节点
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow.val;
}
public ListNode partition( int x) {
if (head == null) {
return null;
}
// write code here
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = head;
while (cur != null) {
if (cur.val < x) {
//第一次插入
if (bs == null) {
bs = be = cur;
} else {
be.next = cur;
be = be.next;
}
cur = cur.next;
} else {
if (as == null) {
//第一次插入
as = ae = cur;
} else {
ae.next = cur;
ae = ae.next;
}
cur = cur.next;
}
}
//第一部分是不是空的，如果空 返回第二部分，如果不为空 进行拼接
if(bs == null) {
return as;
}
//进行拼接
be.next = as;
//后半部分不为空 把后半部分 最后一个节点置空
if(as != null) {
ae.next = null;
}
return bs;
}
public boolean chkPalindrome() {
// write code here
if(head == null) {
return true;
}
//1.找到链表的中间节点
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//2.翻转中间节点 后面的链表
ListNode cur = slow.next;
while(cur != null) {
ListNode curN = cur.next;
cur.next = slow;
slow = cur;
cur = curN;
}
//3. slow从后往前 head从前往后 直到他两相遇
while(head != slow) {
if(head.val != slow.val) {
return false;
}
if(head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
public boolean hasCycle() {
ListNode fast = head;
ListNode slow = head;
while(fast!= null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
fast = head;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
public void createLoop() {
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
//cur指向了 尾结点
cur.next = head.next;
}
}
1.3 链表面试题
1.给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。（leetcode 206）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode cur = head.next;
head.next = null;// 得置为null
while(cur!=null){
ListNode curN = cur.next;
// 开始反转
// head.next = cur.next;
cur.next = head;
head = cur;
cur = curN;
}
return head;
}
}注意：head.next需赋值为空，原因画图理解。
2.给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。（leetcode 876）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
// 快慢指针。理解：一个人的速度是另一个人的速度的2倍，快的人走到终点时慢的人刚好走到中间
if(head == null || head.next==null){
return head;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}注意：
fast!=null && fast.next!=null 不能改为 fast.next!=null && fast!=null，因为fast=null时fast.next会发生空指针异常！！
3.实现一种算法，找出单向链表中倒数第k个节点。返回该结点的值。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public int kthToLast(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for(int i=1;i<=k-1;i++){
fast=fast.next;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow.val;
}
}关键思路：
快指针先走k-1步，则快指针到末尾了慢指针则为倒数第k个
4.将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode();
ListNode tmp = head;
while(list1!=null && list2!=null){
if(list1.val<list2.val){
tmp.next = list1;
tmp = tmp.next;
list1 = list1.next;
}else{
tmp.next = list2;
tmp = tmp.next;
list2 = list2.next;
}
}
if(list1==null && list2!=null){
tmp.next = list2;
}
if(list2==null && list1!=null){
tmp.next = list1;
}
return head.next;
}
}注意：
- 傀儡节点、虚拟节点。
- list1 = list1.next;
list2 = list2.next;
节点后移
5.现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if (pHead == null || pHead.next == null) {
return pHead;
}
// 小于 x 的链表哨兵
ListNode head1 = new ListNode(-1);
ListNode be = head1;
// 大于等于 x 的链表哨兵
ListNode head2 = new ListNode(-1);
ListNode ae = head2;
while (pHead != null) {
ListNode next = pHead.next; // 保存后续节点
pHead.next = null; // 断开原链表
if (pHead.val < x) {
be.next = pHead;
be = be.next;
} else {
ae.next = pHead;
ae = ae.next;
}
pHead = next;
}
// 连接两条链表
be.next = head2.next;
return head1.next;
}
}注意：
如果直接把
pHead节点链接到新的链表里，而不手动把pHead.next = null，那么这些节点还是连着原链表的旧 next，很容易造成 环形链表 或错误拼接。
6.对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针head，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
if(head==null || head.next==null){
return true;
}
// write code here
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
ListNode middle = slow;
ListNode head2 =null;
ListNode cur = middle.next;
while(cur!=null){
ListNode curN = cur.next;
middle.next = null;
cur.next = middle;
middle = cur;
cur = curN;
head2 = middle;
}
ListNode p1 = head;
ListNode p2 = head2;
while(p1.next!=null && p2.next!=null){
if(p1.val == p2.val){
p1=p1.next;
p2=p2.next;
}else{
return false;
}
}
return true;
}
}注意：
1.先找到中间节点
2.反转中间节点之后的部分
3.比较并返回
7.给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lengthA = size(headA);
int lengthB = size(headB);
int count;
if(lengthA>lengthB){
count = lengthA - lengthB;
for(int i=1;i<=count;i++){
headA = headA.next;
}
}else{
count = lengthB - lengthA;
for(int i=1;i<=count;i++){
headB = headB.next;
}
}
while(headA!=null && headB!=null){
if(headA!=headB){
headA=headA.next;
headB=headB.next;
}else{
return headA;
}
}
return null;
}
public int size(ListNode head){
if(head == null){
return 0;
}
int count = 0;
while(head!=null){
head=head.next;
count++;
}
return count;
}
}注意：
1.分别求2个链表的长度，求出差值X
2.让长的链表走X步
3.一起走知道相遇
8.给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null || head.next == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow){
return true;
}
}
return false;
}
}注意：
【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。（相对运动，每次近一个距离）
【扩展问题】
- 为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。- 快指针一次走3步，走4步，...n步行吗？
9.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。（不允许修改 链表）
- 结论：
让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。- 证明：
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
fast = head;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}二、LinkedList
LinkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，LinkedList也实现了List接口，具体如下：
【说明】
- LinkedList实现了List接口
- LinkedList的底层使用了双向链表
- LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
- LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
- LinkedList比较适合任意位置插入的场景
- LinkedList可以当作双向链表使用（实现了List），也可以当作队列使用（实现了Deque）
2.1 LinkedList尝试实现
// 2、无头双向链表实现
public class MyLinkedList {
//头插法
public void addFirst(int data){ }
//尾插法
public void addLast(int data){}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){}
//查找是否包含关键字key是否在链表当中
public boolean contains(int key){}
//删除第一次出现关键字为key的节点
public void remove(int key){}
//删除所有值为key的节点
public void removeAllKey(int key){}
//得到链表的长度
public int size(){}
public void display(){}
public void clear(){}
}public class MyLinkedList {
static class ListNode {
public int val;
public ListNode prev;//前驱
public ListNode next;//后继
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//标志头节点
public ListNode last;//标志尾结点
//得到双向链表的长度
public int size(){
int count = 0;
ListNode cur = head;
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;
}
System.out.println();
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
//是不是第一次插入节点
head = last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
//是不是第一次插入节点
head = last = node;
}else {
last.next = node;
node.prev = last;
last = last.next;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
try {
checkIndex(index);
}catch (IndexNotLegalException e) {
e.printStackTrace();
}
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
//1. 找到index位置
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
//2、开始绑定节点
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
private ListNode findIndex(int index) {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
private void checkIndex(int index) {
if(index < 0 || index > size()) {
throw new IndexNotLegalException("双向链表插入index位置不合法: "+index);
}
}
//删除第一次出现关键字为key的节点
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.prev = null;
}else {
//head == null 证明只有1个节点
last = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next == null) {
//处理尾巴节点
last = last.prev;
}else {
cur.next.prev = cur.prev;
}
}
return;//删完一个就走
}
cur = cur.next;
}
}
//删除所有值为key的节点
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.prev = null;
}else {
//head == null 证明只有1个节点
last = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next == null) {
//处理尾巴节点
last = last.prev;
}else {
cur.next.prev = cur.prev;
}
}
//return;//删完一个就走
}
cur = cur.next;
}
}
public void clear(){
ListNode cur = head;
while (cur != null) {
ListNode curN = cur.next;
//cur.val = null;
cur.prev = null;
cur.next = null;
cur = curN;
}
head = last = null;
}
}
2.2 LinkedList的使用
2.2.1 LinkedList的构造
| 方法 | 解释 |
|---|---|
LinkedList() |
无参构造 |
public LinkedList(Collection<? extends E> c) |
使用其他集合容器中元素构造 List |
注意：
public LinkedList(Collection<? extends E> c)，集合中得是E或者是E的子类。- LinkedList<Integer> list = new LinkedList<>(); 此时的E为Integer
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);2.2.2. LinkedList的其他常用方法介绍
| 方法 | 解释 |
|---|---|
boolean add(E e) |
尾插元素 e |
void add(int index, E element) |
将 element 插入到指定 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) |
截取从 fromIndex 到 toIndex 之间的子列表 |
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println(list);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
list.removeFirst(); // removeFirst(): 删除第一个元素
list.removeLast(); // removeLast(): 删除最后元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list);
// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
if(!list.contains(1)){
list.add(0, 1);
}
list.add(1);
System.out.println(list);
System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
int elem = list.get(0); // get(index): 获取指定位置元素
list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
System.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
List<Integer> copy = list.subList(0, 3);
System.out.println(list);
System.out.println(copy);
list.clear(); // 将list中元素清空
System.out.println(list.size());
}2.2.3 LinkedList的遍历
for循环、for-each、迭代器
- 使用for循环时容易出现问题：如果一边遍历一边删除，size()获得的长度是变化的，可能会跳过某个数据或者报错
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
// foreach遍历
for (int e:list) {
System.out.print(e + " ");
}
System.out.println();
// 使用迭代器遍历---正向遍历
ListIterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+ " ");
}
System.out.println();
// 使用反向迭代器---反向遍历
ListIterator<Integer> rit = list.listIterator(list.size());
while (rit.hasPrevious()){
System.out.print(rit.previous() +" ");
}
System.out.println();
}2.3 ArrayList和LinkedList的区别
| 不同点 | ArrayList | LinkedList |
|---|---|---|
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持，时间复杂度 O(1) |
不支持，时间复杂度 O(N) |
| 头插 | 需要搬移元素，效率低 O(N) |
只需修改引用指向，时间复杂度 O(1) |
| 插入 | 空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储 + 频繁访问 | 任意位置插入和删除频繁 |