线性表 ArrayList

顺序表

数组：删除结点时，可以用0表示，这个位置必须有元素

顺序表：有序的序列，涉及移动

ArrayList作为顺序表，它的增删改查

ArrayList是基于数组实现的动态数组

• add
  • 队尾插入 easy
  • 中间插入（使用位移的方式挪动）
    • System.arraycopy(elementData, index, elementData, index + 1,size - index);
    • 扩容

链表

定义：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的

单链表

class Node{
    Object data;
    Node next;
}

双链表

private static class Node<E>{
    E item;
    Node<E>next;
    Node<E>prev;
}

LinkedList 就是用双向链表实现的

总结

	优点	缺点	应用
顺序表	存储空间连续允许随机访问尾插，尾删方便	插入效率低删除效率低长度固定	哪哪都在用？
单链表	随意进行增删改插入效率高删除效率高 长度可以随意修改	内存不连续不能随机查找	Android： MessageQueue JavaEE：HashMap Redis
双链表	随意进行增删改插入效率高删除效率高长度可以随意修改查找效率比单链表快一倍	内存不连续不能随机查找，但是效率比单链表快一倍	应用：linkedList

链表实现LRU算法

（1）缓存

1. 硬件缓存

CPU缓存：位于CPU与内存之间的临时存储器。解决CPU速度和内存速度的速度差异问题。

2. 软件缓存

   内存缓存——预先将数据写到了容器(list,map,set)等数据存储单元中，就是软件内存缓存

   数据库缓存

   网络缓存

（2）内存缓存淘汰机制

如何踢掉不用的数据

1. FIFO （First In, First Out）队列

2. LFU (Least Frequently Used) 将使用最不频繁的这些内存块给剔除掉

3. LRU (Least Recently Used) 最近最少使用 （将古老的踢出）

LRU

1. 新数据插入到链表头部
2. 当缓存命中(即缓存数据被访问)，数据要移到表头
3. 当链表满的时候，将链表尾部的数据丢弃

单链表实现LRU算法

//单链表
class LinkedList<T>{
    Node list;
    int size;
    
    //增
    
    //删
    
    //改
    
    
    //查
    
    
    
    class Node{
        T data;
        Node next;
        
        public Node(T data,Node node){
            this.data = data;
            this.next = node; //-----------该节点是原来节点的下一个---------------
        }
    }
}

面试

1.ArrayList的大小是如何自动增加的？（ArrayList如何扩容）

ArrayList是基于数组实现的动态数组，当元素数量超过当前数组容量时，它会自动扩容。

int newCapacity = oldCapacity + (oldCapacity >> 1);

在grow()方法中，使用位运算进行扩容操作，将容量变为原来的1.5倍

• 创建一个新的数组，为原来大小的1.5倍
• 使用数组工具类Arrays里面的一个方法，copyOf，将原数组的内容拷贝到新数组中
• 完成扩容之后再把新的数据加到这新的数组里面就OK了

2.什么情况下你会使用ArrayList?

（使用场景）就要知道其优缺点

优点： 尾插效率高，支持随机访问（内部是数组实现的）。

缺点： 中间插入或者删除效率低。（会使用System.arraycopy）

增加/删除结点多的情况、排序等等不要使用ArrayList
如果查找（需要频繁随机访问） 需要顺序存储和遍历、不需要频繁插入和删除or尾部插入操作比较多

3.在索引中ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?

对 很低，因为涉及到很多System.arraycopy操作，耗时间、耗内存

4.ArrayList如何顺序删除节点

从后向前删除：直接使用for循环，，不会影响前面的索引

从前往后删除：使用迭代器顺序删除：

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    iterator.next();  // 必须先调用 next() 获取当前元素
    iterator.remove();  // 删除当前元素
}

5.arrayList的遍历方法

1. 使用 for 循环

通过索引遍历 ArrayList，适合需要访问索引的场景。

2. 使用增强 for 循环

直接遍历 ArrayList 中的元素，适合不需要访问索引的场景。

3. 使用迭代器（Iterator）

通过 Iterator 遍历 ArrayList，适合需要删除元素的场景。

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();  // 获取当前元素
    System.out.println(element);
}

4. 使用 forEach 方法（Java 8+）

通过 forEach 方法遍历 ArrayList，适合函数式编程风格。

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

list.forEach(element -> System.out.println(element));  // 使用 Lambda 表达式

5. 使用 Stream API（Java 8+）

通过 Stream API 遍历 ArrayList，适合需要过滤、映射等操作的场景。

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

list.stream().forEach(element -> System.out.println(element));  // 使用 Stream API

优点1.支持链式操作（如过滤、映射、排序等）2.适合处理复杂逻辑。

ArrayList（动态数组）与LinkedList（双链表）的区别？

ArrayList（动态数组）和 LinkedList（双链表）是 Java 中两种常用的数据结构，它们各有特点和适用场景。以下是它们之间的主要区别：

1. 数据结构

• ArrayList：基于动态数组实现，存储元素在内存中是连续的。
• LinkedList：基于双链表实现，存储元素在内存中可以是不连续的，每个元素（节点）包含指向前后节点的引用。

2. 内存使用

• ArrayList：内存使用相对较节省，但在扩展时需要复制原数组元素到新数组。
• LinkedList：每个节点需要额外的存储空间来保存指针，因而额外的内存开销更大。

3. 访问速度

• ArrayList：支持随机访问，使用索引访问元素的时间复杂度为 O(1)。
• LinkedList：访问元素时需要从头开始遍历（或从尾开始），时间复杂度为 O(n)。

4. 插入和删除

• ArrayList：在中间插入或删除元素时，需要移动后面的元素，时间复杂度为 O(n)。
• LinkedList：在任意位置插入或删除元素只需调整指针，时间复杂度为 O(1)（已知节点时）。

5. 性能

• ArrayList：在查找频繁但插入删除不多的情况下表现较好。
• LinkedList：在频繁插入和删除的情况下表现更好，特别是在列表的两端。

6. 用途

• ArrayList：适用于需要频繁访问元素的场景，如列表、队列。
• LinkedList：适合需要频繁插入和删除操作的场景，如实现队列、栈等。

总结

选择 ArrayList 还是 LinkedList 应根据你的具体需求而定。如果你主要关心快速访问元素，可以选择 ArrayList；如果你需要频繁进行插入和删除操作，LinkedList 可能更合适。如果你还有其他问题或者需要进一步的解释，随时告诉我！

6.手写一个单链表，并且实现单链表元素的逆置，（a0, a1,a2,a3,..an）-> (an,an-1,… a1, a0),算法的空间复杂度和时间复杂度经可能低。

逆置单链表的常见方法有两种：迭代法和递归法。

定义3个节点分别是preNode,curNode,nextNode. 先 将curNode的next赋值给nextNode, 再curNodel的next 指向 preNode.至此curNode的指针调整完毕。 然后往后移动 curNode, 将curNode赋值给preNode，将nextNode赋值给curNode，如此循环到curNode==null为止

1 -> 2 -> 3 -> 4 -> 5 -> 6

null <- 1 <- 2 <- 3 <- 4 <- 5 <- 6

//Node链表结点
class Node{
    int data;
    Node next;
    //构造函数
    public Node(int data){
        this.data = data;
        this.next = null;
    }
}
//单链表
class LinkedList{
    Node head;
    //添加元素到链表末尾
    public void add(int data){
        Node newNode = new Node(data);
        if(head == null){
            head = newNode;
        }else{
            Node current = head;
            while(current.next != null){
                current = current.next;
            }
            current.next = newNode;
        }
    }
    
    //打印链表
    public void print(){
        Node current = head;
        while(current != null){
            System.out.print(current.data + "->");
            current = current.next;
        }
        System.out.println("null");
    }
    
    
    
    //单链表的逆置实现
    public void reverse(){
        Node prev = null;
        Node current = head;
        Node next = null;
        
        while(current != null){
            next = current.next;//保存下一个节点
            current.next = prev; //反转当前结点的指针
            
            prev = current; //prev前移
            current = next; //current前移
        }
        head = prev; //更新头结点
    }

    
}//LinkedList类


//测试
public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        
        System.out.println("原始链表:");
        list.print();  // 1 -> 2 -> 3 -> 4 -> null
        
        list.reverse();
        System.out.println("逆置后链表:");
        list.print();  // 4 -> 3 -> 2 -> 1 -> null
    }
}

//-------------------------------------------------
public static Node reverseListNode(Node head){
	//单链表为空或只有一个节点，直接返回原单链表
    if (head == null || head.getNext() == null){ 
        return head;
    }
    //前一个节点指针
    Node preNode = null;
    //当前节点指针
    Node curNode = head;
    //下一个节点指针
    Node nextNode = null;
    while (curNode !=  null){ 
        nextNode = curNode.getNext();//nextNode 指向下一个节点
        curNode.setNext(preNode);//将当前节点 next域指向前一个节点
        preNode = curNode;//preNode 指针向后移动
        curNode = nextNode;//curNode指针向后移动
    }
    return preNode;
}

26：https://leetcode.com/problems/remove-duplicates-from-sorted-array/

35：https://leetcode.com/problems/search-insert-position/

34：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

21合并两个有序链表：https://leetcode.com/problems/merge-two-sorted-lists/

24两两交换链表中的相邻节点 （中）（迭代 哨兵）：https://leetcode.com/problems/swap-nodes-in-pairs/

138复制带随机指针的链表 （中）：https://leetcode.com/problems/copy-list-with-random-pointer/

Donate