数据结构~基础1~线性表【《数组、链表、栈、队列》的设计】

简介: 数据结构~基础1~线性表【《数组、链表、栈、队列》的设计】

数据结构~基础1~线性表【《数组、链表、栈、队列》的设计】


 

1, 数组 【顺序存储,元素地址是连续的】

■  索引

■  数组的致命缺点:无法修改容量

动态数组


51.png


□  添加、删除逻辑:挪动空间

  □  添加:从最后一个元素开始到插入位置的元素,往后挪【当前元素覆盖后一个元素】

  □  删除:从当前删除元素的后一个元素开始到最后一个元素,往前挪【当前元素覆盖前一个元素】

//添加
for(int i = size - 1; i >= index; i--) {
    elements[i + 1] = elements[i];
}
//删除
for(int i = index + 1; i <= size - 1; i++){
    elements[i - 1] = elements[i];
}

● 补充一下代码性能的优化:


52.png

53.png

54.png


□    缩容同理

■   JDK中内置了一个动态数组类:java.util.ArrayList

 

2,链表

■  动态数组有个明显的缺点:可能会造成内存空间的大量浪费


55.png


■  结点添加、删除:


//添加【头指针情况--要分类,分是否插入到第一个位置】:
if (index == 0) {//第一个位置
    first = new Node<>(element, first);
} else {//其他位置:先找到插入结点的前一个结点prev
    Node<E> prev = node(index - 1);
    //当前结点的next先指向prev的后一个结点,然后prev的next再指向当前结点
    prev.next = new Node<>(element, prev.next);
}
//删除结点【头指针情况--要分类,分是否插入到第一个位置】:
if (index == 0) {
    first = first.next;
} else {
    Node<E> prev = node(index - 1);
    prev.next = node.next;
}
//添加【头结点情况--也要分类,只是分类完可以同一处理】
Node<E> preNode = (index == 0) ? first : node(index - 1);
preNode.next = new Node<E>(element, preNode.next);
//删除结点头结点情况--也要分类,只是分类完可以同一处理】
Node<E> preNode = (index == 0) ? first : node(index - 1);
preNode.next = preNode.next.next;

 

2-1,链表【升级】

■   JDK中内置了一个动态链表类:java.util.LinkedList


56.png


■  添加和删除

//添加【双向链表】——【分类:添加到最后位置时(这里还要考虑空链表的情况), 其他位置(还要考虑到添加到第一个位置时)】
        // size == 0
        // index == 0
        if (index == size) { // 往最后面添加元素
            Node<E> oldLast = last;
            last = new Node<>(oldLast, element, null);
            if (oldLast == null) { // 这是链表添加的第一个元素
                first = last;
            } else {
                oldLast.next = last;
            }
        } else {    //  添加到其他位置
            Node<E> next = node(index); 
            Node<E> prev = next.prev; 
            Node<E> node = new Node<>(prev, element, next);
            next.prev = node;
            if (prev == null) { // index == 0【添加到第一个位置】
                first = node;
            } else {
                prev.next = node;
            }
        }


3,栈
栈是一种特殊的线性表,只能在一端进行操作。【入栈、出栈 都是栈顶那一端】

 后进先出的原则

 入栈push( );  出栈 pop( );   栈顶peek( );

 java中使用Deque的LinkedList实现

 

4,队列

队列是一种特殊的线性表,只能在头尾两端进行操作

 先进先出的原则

 只能在尾部入队:入队offer( );  只能在头部出栈:出队poll( );   队顶peek( );

 java中使用Queue的LinkedList实现

目录
相关文章
|
6天前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
24 8
【数据结构OJ题】合并两个有序链表
|
7天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
10 1
【数据结构OJ题】链表中倒数第k个结点
|
4天前
【数据结构OJ题】链表分割
牛客题目——链表分割
5 0
【数据结构OJ题】链表分割
|
5天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
7 0
【数据结构OJ题】链表的回文结构
|
7天前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
10 0
【数据结构OJ题】链表的中间结点
|
7天前
【数据结构OJ题】反转链表
力扣题目——反转链表
10 0
【数据结构OJ题】反转链表
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
1月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
1月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
14 2
|
2月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
30 1