数据结构——顺序表与链表

1. 基础介绍

1、线性结构：

如果一个数据元素序列满足：

（1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；

（2）第一个数据元素没有前驱数据元素；

（3）最后一个数据元素没有后继数据元素。

则称这样的数据结构为线性结构。

2. 线性表

线性表 （linear list） 是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤ 的数据结构，常⻅的线性表：顺序表、链表、栈、队列。

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

3. 顺序表

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

2. List介绍

1. list（线性表）

在集合框架中，List是⼀个接⼝，继承⾃Collection

Collection也是⼀个接⼝，该接⼝中规范了后序容器中常⽤的⼀些⽅法。

方法	解释
boolean add (E e)	尾插 e
void add (int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o，传入的是一个对象
E get (int index)	获取下标 index 位置元素
E set (int index, E element)	将下标 index 位置元素设置为 element
void clear ()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)	截取部分list，前开后闭

        List<Integer> list1 = new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);list1.add(4);list1.add(5);//当我们想删除2这个元素list1.remove(new Integer(5));System.out.println(list1);List<Integer> list3 = list1.subList(1,3);//截取[1,3)list3.set(0,188);System.out.println(list3);System.out.println(list1);

为什么改变 list3 中的值，list1 也会改变？

2. ArrayList（顺序表）

方法	解释
ArrayList ()	无参构造
ArrayList(Collection<? extends E> c)	利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)	指定顺序表初始容量

ArrayList(Collection<? extends E> c)：

能够引用的类一定是E或E的子类

    public static void main(String[] args) {List<Integer> list1 = new LinkedList<>();//LinkedList是List接口的一个实现类，它使用链表数据结构来存储元素list1.add(1);list1.add(2);list1.add(3);List<Integer> list = new ArrayList<>(list1);//将list1中的所有元素复制到新的ArrayList中list.add(1314);System.out.println(list);}

3. Linkedlist（链表）

方法	解释
LinkedList()	无参构造

List 的官方文档：    List (Java Platform SE 8 )

ArrayList 的官方文档：      ArrayList (Java Platform SE 8 )

LinkedList 的官方文档：     LinkedList (Java Platform SE 8 )

3. ArrayList介绍

在集合框架中，ArrayList是⼀个普通的类，实现了List接⼝，具体框架图如下：

【说明】

1. ArrayList是以泛型⽅式实现的，使⽤时必须要先实例化

2. ArrayList实现了RandomAccess接⼝，表明ArrayList⽀持随机访问

3. ArrayList实现了Cloneable接⼝，表明ArrayList是可以clone的

4. ArrayList实现了Serializable接⼝，表明ArrayList是⽀持序列化的

5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使⽤，在多线程中可以选择Vector或者CopyOnWriteArrayList

6. ArrayList底层是⼀段连续的空间，并且可以动态扩容，是⼀个动态类型的顺序表

 底层扩容

迭代器

一般情况下，能够直接通过 sout 输出引用指向对象当中的内容的时候，此时一定重写了 toString 方法

导入包    ： import java.util.Iterator;

 ArrayList<Integer> list2 = new ArrayList<>();list2.add(10);list2.add(20);list2.add(30);list2.add(40);System.out.println(list2);//一般情况下，能够直接通过 sout 输出引用指向对象当中的内容的时候，此时一定重写了 toString 方法System.out.println("===================");//迭代器//方法1：Iterator<Integer> it = list2.iterator();//判断下一个数据是否存在while (it.hasNext()){System.out.print(it.next()+" ");//打印it的下一个数据}System.out.println();System.out.println("===================");//方法2：ListIterator<Integer> it2 = list2.listIterator();//判断下一个数据是否存在while (it2.hasNext()){System.out.print(it2.next()+" ");//打印it2的下一个数据}System.out.println();System.out.println("===================");

如果我们想逆序打印呢

        //逆序打印ListIterator<Integer> it3 = list2.listIterator(list2.size());//判断上一个数据是否存在while (it3.hasPrevious()){System.out.print(it3.previous()+" ");//打印it3的上一个数据}System.out.println();System.out.println("===================");

         

List<List<E>>  list = new ArrayList<>();

这种结构在Java中表示一个包含多个列表的列表

List<List<E>>: 这是一个泛型声明，表示一个列表的列表。外层列表的每个元素都是一个List<E>，即一个包含类型为E的元素的列表。

ArrayList的问题及思考：

1. ArrayList底层使⽤连续的空间，任意位置插⼊或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)

2. 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。

3. 增容⼀般是呈1.5倍的增⻓，势必会有⼀定的空间浪费。

4. 链表介绍

链表是⼀种 物理存储结构上⾮连续 存储结构，数据元素的逻辑顺序是通过链表中的引⽤链接次序实现的 。

区别	ArrayList	LinkedList
内部实现	基于动态数组实现。 底层使用一个数组来存储元素，当数组容量不足时，会自动扩容（通常是当前容量的1.5倍）。 适合随机访问（通过索引访问元素）。	基于双向链表实现。 每个元素是一个节点，包含数据和指向前后节点的指针。 适合频繁的插入和删除操作。
随机访问	通过索引访问元素的时间复杂度为 O(1)，非常高效。	通过索引访问元素的时间复杂度为 O(n)，需要从头或尾遍历链表。
插入和删除	在数组末尾插入或删除元素的时间复杂度为 O(1)。 在数组中间插入或删除元素的时间复杂度为 O(n)，因为需要移动后续元素。	在链表头部或尾部插入或删除元素的时间复杂度为 O(1)。 在链表中间插入或删除元素的时间复杂度为 O(n)，因为需要遍历链表找到目标位置。
内存占用	内存占用相对较小，因为底层是连续的数组。	内存占用相对较大，因为每个节点需要额外存储前后指针
适用场景	适合频繁的随机访问操作。 适合在数组末尾频繁插入和删除元素。 适合存储大量数据，且数据量相对固定。	适合频繁的插入和删除操作，尤其是在链表头部或尾部。 适合实现队列（Queue）或双端队列（Deque）。 适合数据量变化较大的场景。

总结

• ArrayList：

  • 优点：随机访问高效，内存占用小。

  • 缺点：插入和删除操作（尤其是中间位置）较慢。

  • 适用场景：频繁随机访问，数据量相对固定。

• LinkedList：

  • 优点：插入和删除操作（尤其是头部和尾部）高效。

  • 缺点：随机访问较慢，内存占用大。

  • 适用场景：频繁插入和删除操作，数据量变化较大。

简单的洗牌算法

import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class CardDom {static class Card{public int rank;//牌面值public String suit;//花色public Card(int rank,String suit){this.rank = rank;this.suit = suit;}@Overridepublic String toString() {return "["+rank + " "+ suit+"]" ;}}public static final String[] SUITS = {"♠","♥","♣","♦"};//有一副牌private static List<Card> buyDeck(){List<Card> deck = new ArrayList<>();//创建一个链表存放牌for(int i=0;i<SUITS.length;i++){for(int j=1;j<=13;j++){Card card = new Card(j,SUITS[i]);deck.add(card);//将牌插入}}return deck;}//将交换牌的位置private static void swap(List<Card> deck, int i, int j){Card t = deck.get(i);deck.set(i,deck.get(j));deck.set(j,t);}//洗牌private static void shuffle(List<Card> deck){Random random = new Random();for(int i=deck.size()-1;i>0;i--){int j = random.nextInt(i);swap(deck,i,j);}}//每人发五张牌public static void main(String[] args) {List<Card> desk = buyDeck();System.out.print("买回来的牌:");System.out.println(desk);shuffle(desk);System.out.print("洗过的牌：");System.out.println(desk);List<List<Card>> heads = new ArrayList<>();//三个人玩牌List<Card> head0 = new ArrayList<>();//存放第一个人的牌List<Card> head1 = new ArrayList<>();//存放第二个人的牌List<Card> head2 = new ArrayList<>();//存放第三个人的牌heads.add(head0);heads.add(head1);heads.add(head2);//控制次数for(int i=0;i<5;i++){for (int j=0;j<3;j++){//每次拿零下标的牌Card card=desk.remove(0);//从牌中拿出第一张牌heads.get(j).add(card);//每个人拿到的牌存入对应的顺序表}}System.out.print("第一个人拿的牌");System.out.println(head0);System.out.print("第二个人拿的牌");System.out.println(head1);System.out.print("第三个人拿的牌");System.out.println(head2);System.out.print("剩下的牌：");System.out.println(desk);}}