本文详细介绍了数据结构中的线性表，包括顺序表与链表的区别，线性结构与非线性结构的特性，并通过实例解析了ArrayList、LinkedList和Vector的优缺点。接着，文章深入探讨了List接口及其常用方法，展示了ArrayList和LinkedList的实现。此外，文章还讲解了栈和队列的概念、操作以及应用，并分析了Map和Set的特点，包括底层结构如HashMap和HashSet。内容涵盖了搜索树和哈希表，为理解这些基本数据结构提供了全面的指导。
目录
2.ArrayList，LinkedList ，Vector区别
3.List/Arraylist/LinkedList常用方法(add remove get set contains clear indexOf )
2.栈的使用方法(push pop peek size empty)
2.队列的使用方法(offer poll peek size isEmpty)
一，线性表
线性表：由n(n>0)个数据元素(数字，字符等)所构成的有限序列，逻辑连续（一条直线），物理上不一定连续，分为顺序表和链表
1.顺序表和链表区别
1.顺序表：1.能存储的数据有限（一次开辟，永久使用），但是易于操作、编写代码
2.空间利用率相对高
3.若查改元素，其时间复杂度低O(1)，可根据数组下标直接访问；
若增删移其时间复杂度高，至少 O(n)，会牵涉到大量元素的整体移动
2.链表： 1.能存储的数据取决于堆的内存大小（存一个开辟一个空间）
2.空间利用率相对低，有空间碎片产生
3.若查改元素，其时间复杂度高，至少 O(n)，需要指针遍历找到指定节点；
若增删移其时间复杂度低O(1)，在链表中某处插入或删除节点时，只需改变相应节点的指针指向即可
2.线性结构与非线性结构区别
1.线性：数据元素存在一对一的对应关系，有两种不同的存储结构，顺序存储结构（数组，顺序表）和链式存储结构（链表），常见的有数组，队列，链表和栈
2.非线性： 数据元素不再保存在一个线性序列中，可一对零/多，常见的有二维数组，多维数组，广义表，树(二叉树等)
3.图片展示
图1来自 UniqueUnit
图2来自Fei@
二，List(列表)
1.什么是List
（1）List 是接口，继承至Collection接口，使用时必须去实例化List的实现类ArrayList,LinkedList
（2）List包含，ArrayList, LinkedList , Vector
2.ArrayList，LinkedList ，Vector区别
1.ArrayList的优缺点
ArrayList是基于动态的数组的数据结构
优点：底层数据结构是数组，查询快，增删慢。
缺点： 线程不安全，效率高
2.LinkedList的优缺点
LinkedList是基于链表的数据结构
优点：底层数据结构是链表，查询慢，增删快。
缺点： 线程不安全，效率高
3.Vector的优缺点
在ArrayList中每个方法中添加了synchronized关键字来保证同步
优点：底层数据结构是数组，查询快，增删慢。
缺点：线程安全，效率低
4.总结
查询次数多：ArrayList
修改次数多：LinkedList
安全性高：Vector
注意：
并不是说ArrayList查找快，LinkedList增删快
而是说，ArrayList具备随机访问能力(类似闪现)，来获取元素的位置，再用indexOf查找，所以快
而LinkedList，首尾增删O(1),中间位置还是O(N),但这里不是链表不行，而是封装以后的LinkedList不行
ps:C++ LinkedList 都为O(1)
3.List/Arraylist/LinkedList常用方法(add remove get set contains clear indexOf )
尾插 e： boolean add(E e)
将 e 插入到 index 位置： void add(int index, E element)
尾插 c 中的元素： boolean addAll(Collection<? extends E> c)
删除 index 位置元素： E remove(int index)
删除遇到的第一个 o： boolean remove(Object o)
获取下标 index 位置元素： E get(int index)
将下标 index 位置元素设置为 element：E set(int index, E element)
清空： void clear()
判断 o 是否在线性表中： boolean contains(Object o)
返回第一个 o 所在下标： int indexOf(Object o)
返回最后一个 o 的下标： int lastIndexOf(Object o)
截取部分 list： List<E> subList(int fromIndex, int toIndex)
4.详解ArrayList
(1).什么是ArrayList
在集合框架中，ArrayList是一个普通的类，是List接口的大小可变数组的实现（结构体+数组）
特点：1.支持随机访问
2.可以clone
3. 支持序列化
4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表 6.自动扩容(Arrays.copyOf(elem,2*elem.length))
(2).ArrayList的构造
空列表： List<Integer> list1 = new ArrayList<>();
具有10个容量： List<Integer> list2 = new ArrayList<>(10);
与list2中的元素一致：ArrayList<Integer> list3 = new ArrayList<>(list2);
注意：一定不能省略类型，若任何类型的元素都可以存放，将会发生混乱
(3).MyArrayList的实现
import java.util.Arrays;
public class MyArraylist {
public int[] elem;
public int usedSize;//默认容量
private static final int DEFAULT_SIZE = 10;
public MyArraylist() {
this.elem = new int[DEFAULT_SIZE];
this.usedSize=0;
}
//打印顺序表
public void display() {
for (int i = 0; i <this.usedSize ; i++) {
System.out.print(this.elem[i]);
}
System.out.println();
}
// 新增元素,默认在数组最后新增
public void add(int data) {
if(isFull()){
this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize]=data;
this.usedSize++;
}
//判断当前的顺序表是不是满的！
public boolean isFull() {
return this.elem.length==this.usedSize;
}
//检查位置是否合法
private boolean checkPosInAdd(int pos) {
if(pos<0||pos>this.usedSize){
System.out.println("pos位置不合法");
return false;
}
return true;//合法
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
if(isFull()){
//数组满了，就扩容
this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
}
for(int i=this.usedSize-1;i>=pos;i--){
this.elem[i+1]=elem[i];
}
this.elem[pos]=data;
this.usedSize++;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for(int i=0;i<this.usedSize;i++){
if(toFind==this.elem[i]){
return true;
}
}
return false;
}
// 查找某个元素对应的位置
public int indexOf(int toFind) {
for(int i=0;i<this.usedSize;i++){
if(toFind==this.elem[i]){
return i;
}
}
return -1;
}
// 获取 pos 位置的元素
public int get(int pos) {
return this.elem[pos];
}
//判断是否为空
private boolean isEmpty() {
return this.usedSize==0;
}
// 给 pos 位置的元素设为【更新为】 value
public void set(int pos, int value) {
this.elem[pos]=value;
}
// 删除第一次出现的关键字key
public void remove(int key) {
for(int i=0;i<this.usedSize;i++){
if(key==this.elem[i]){
for(int j=i;j<this.usedSize-1;j++){
this.elem[j]=this.elem[j+1];
}
this.usedSize--;
return;
}
}
System.out.println("不存在你要删除的数据");
}
// 获取顺序表长度
public int size() {
return this.usedSize;
}
// 清空顺序表
public void clear() {
this.usedSize=0;
}
}(4).例题
力扣 杨辉三角
答案：
class Solution {
public static List<List<Integer>> generate(int num){
List<List<Integer>> list=new ArrayList<>();
int[][]array=new int[num][num];
for (int i = 0; i < num; i++) {
List<Integer> subList=new ArrayList<>();
for(int j=0;j<=i;j++){
if(j==0||j==i){
array[i][j]=1;
}else{
array[i][j]=array[i-1][j-1]+array[i-1][j];
}
subList.add(array[i][j]);
}
list.add(subList);
}
return list;
}
}5.详解LinkedList
(1).什么是LInkedList
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用（指针）链接次序实现的,是List接口链表的实现（结构体+指针）
简述：通过节点连接元素的序列
特点：
1.逻辑连续，物理不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.空间分配具有策略，两次申请的空间可能一样，也可能不一样
4.底层使用了双向链表
5.不支持随机访问
6.插入和删除元素，首尾时间复杂度为O(1)，中间还为O(N)
分类：
1.单向or双向
2.带头or不带头
3.循环or非循环
(2).什么是节点（Node类）
1.链表由一系列节点（链表中每一个元素称为结点）组成，节点可以在运行时动态生成。
2.每个节点包括两个部分：存储数据元素的数据域，存储下一个节点地址的指针域。
如图：
3.代码实现
private static class Node<E> {
E val;//所存数据
Node<E> next;//指向下一个节点的引用（指针）
Node<E> prev;//指向上一个节点的引用（指针）
Node(E val, Node<E> next, Node<E> prev) {
this.val = val;
this.next = next;
this.prev = prev;
}
}
最低0.47元/天 解锁文章
扫一扫
3344
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
