当前位置：首页 > ops >正文

数据结构顺序表与链表

ops 2025/6/26 14:53:15

文章目录

- 📕1. 线性表（linear list）
- 📕2. ArrayList与顺序表
- - - ✏️2.1 顺序表的概念
    - ✏️2.2 ArrayList简介
    - ✏️2.3 ArrayList的构造
    - ✏️2.4 ArrayList常见操作
    - ✏️2.5 ArrayList的遍历
    - ✏️2.6 ArrayList的自动扩容机制
    - ✏️2.7 ArrayList常用方法的具体实现代码（重点！！！）
    - ✏️2.8 ArrayLsit当前面临的问题
- 📕3. LinkedList与链表
- - - ✏️3.1 链表的概念
    - ✏️3.2 LinkedList简介
    - ✏️3.3 LinkedList的构造
    - ✏️3.4 LinkedList常见操作
    - ✏️3.5 LinkedList常用方法的具体实现代码（重点！！！）
- 📕4. ArrayList和LinkedList的区别

📕1. 线性表（linear list）

在集合框架中，List是一个接口。从数据结构的角度看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

常见的线性表：顺序表、链表、栈、队列……

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

线性结构规定：一个元素只能有一个前驱，一个后继。如果有多个前驱或后继，就不是线性结构。

💡注意：List是个接口，并不能直接用来实例化。

如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口。

ArrayList ⇒ 顺序表
LinkedList ⇒ 链表

📕2. ArrayList与顺序表

✏️2.1 顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
在数组上完成数据的增删查改。

✏️2.2 ArrayList简介

在集合框架中，ArrayList是⼀个普通的类，实现了List接口，具体框架图如下：
在这里插入图片描述

💡注意：

1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

✏️2.3 ArrayList的构造

方法	解释
ArrayList()	无参构造
ArrayList(int initialCapatity)	指定顺序表初始容量

public static void main(String[] args) {List<Integer> l1 = new ArrayList<>(); //实例化一个空表，推荐写法List<Integer> l2 = new ArrsyList<>(10); //实例化一个初始容量为10的空表List<Integet> l3 = new ArrayList<>(l2); //实例化出的l3,与l2中的元素一致
}

✏️2.4 ArrayList常见操作

ArrayList虽然提供的方法比较多，但是常用方法如下所示，需要用到其他方法时，可以查看JAVA帮助手册。（可以我找要）

方法	解释
boolean add(E e)	尾插e
void add(int index,E e)	把e插入到 index位置
E remove（int index）	删除index位置的元素
E get(int index)	获取index位置的元素
E set(int index,E e)	将index位置元素设置为e
void clear()	清空
boolean contains(Object o)	判断o是否在线性表中
int indexof(Object o)	返回第一的o所在的下标
int lastindexof(Object o)	返回最后一个o所在下标

💡特别提醒：虽然ArrayList中提供了常见的方法，但是我们仍需掌握方法的底层原理。

✏️2.5 ArrayList的遍历

ArrayList可以使用三种方法进行遍历：

for循环

public static void main(String[] args) {List<Integer> l1 = new ArrayList<>();l1.add(1);l1.add(2);l1.add(3);l1.add(4);l1.add(5);	l1.add(6);for(int i = 0;i<l1.size();i++){System.out.println(l1.get(i));}
}

for-each

public static void main(String[] args) {List<String> l2 = new ArrayList<>();l2.add("1");l2.add("2");l2.add("3");l2.add("4");for (String l : l2){System.out.println(l);}
}

注意：并不是所有的类都能写进for-each循环中，写进for-each循环中的类要求必须实现Iterable接口

迭代器

public static void main(String[] args) {List<String> l3 = new ArrayList<>();l3.add("1");l3.add("2");l3.add("3");l3.add("4");Iterator<String> iterator = l3.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}}