list是先入什么出

### List 数据结构的特点

List 是一种线性数据结构，支持顺序访问和随机访问。根据具体实现方式的不同，List 可能基于数组或链表构建。

#### 基于数组的 List (ArrayList)

- **特点**
- 支持快速随机访问，时间复杂度 O(1)[^1]。
- 插入和删除操作较慢，在最坏情况下需要移动大量元素，时间复杂度为 O(n)，其中 n 表示列表中的元素数目。

#### 基于链表的 List (LinkedList)

- **特点**
- 不支持高效的随机访问，每次查找都需要从头开始遍历，平均时间复杂度为 O(n)[^2]。
- 提供高效插入和删除功能，特别是在已知位置的情况下，只需调整相邻节点之间的链接即可完成操作，时间复杂度接近常数级别 O(1)。
- 链接结点包含前驱(pre) 和 后继(next) 的指针字段，使得双向遍历成为可能。

关于先进先出(FIFO, First In First Out) 或者后进先出(LIFO, Last In First Out):

- 如果将 LinkedList 当作栈(Stack) 使用，则遵循 LIFO 原则；
- 若作为队列(Queue) 来使用，则体现 FIFO 特征[^4]。

对于 Redis 中的 List 类型，默认行为更倾向于双端队列(Double-ended Queue)，既可以从头部也可以从尾部进行 push/pop 操作，因此既可以表现出FIFO特性也能展现LIFO特性。

// Java 实现简单的单向链表表示法下的 List 添加方法
public class ListNode {
    int val;
    ListNode next;

    public ListNode(int x) { 
        this.val = x; 
    }
}

class MyLinkedList {
    private ListNode head;
    
    // 在链表末尾添加新元素
    public void addAtTail(int val){
        ListNode newNode = new ListNode(val);
        if(head == null){
            head = newNode;
        }else{
            ListNode current = head;
            while(current.next != null){
                current = current.next;
            }
            current.next = newNode;
        }
    }
}