Java-Collection1ListArrayList顺序表LinkedList链表
目录
Java Collection(1)——List——ArrayList(顺序表)&LinkedList(链表)
一.认识List
1.什么是List？
List是Java标准库中的一个接口，下面是List和其他接口/类的关系图
2.List常用方法简介
1.boolean add(E e)
2.void add(int index, E element)
3.E remove(int index)
4.boolean remove(Object o)
5.E get(int index)
6.E set(int index, E element)
7.void clear()
二.ArrayList(顺序表)
1.什么是ArrayList？
简介：
ArrayList是Java标准库中的一个类，实现了List接口。顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改
特点：
动态大小：快速随机访问：通过下标访问元素，时间复杂度是O(1)存储任意类型的数据：支持存储任意类型的数据，包括基本数据类型(自动装箱)线程不安全：Vector(使用了synchronized)可以看作是ArrayList的线程安全版本，线程安全问题看我相关的博文
2.模拟实现ArrayList
1.创建ArrayList
实际上就是创建一个数组
2.添加元素
3.在pos位置添加元素
4.判断某元素是否存在
5.找到目标元素下标
6.判断输入下标是否合法
7.获取pos位置的元素
8.将pos位置元素改为value
9.删除第一次出现的目标元素
10.清空顺序表
3.模拟实现的ArrayList的源码
class MyArrayList<T>{
private int[] array;
private int usedSize;
private static final int DefaultSize = 2;
//无参构造方法
public MyArrayList(){
this.array = new int[DefaultSize];
}
//有参构造方法
public MyArrayList(int initCapacity){
this.array = new int[initCapacity];
}
//打印
public void show(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.array[i]+" ");
}
System.out.println();
}
//判断是否满了
public Boolean isFull(){
if (this.array.length == this.usedSize)
return true;
else
return false;
}
//从最后一个位置添加元素
public void add(int data){
if (isFull()){
this.array = Arrays.copyOf(this.array,this.array.length*2);
}
this.array[this.usedSize] = data;
this.usedSize++;
}
//在pos位置添加元素
public void add(int pos,int data){
if (pos < 0 || pos > this.usedSize)
throw new exception(pos+"位置不合法");
if (isFull()){
this.array = Arrays.copyOf(this.array,this.array.length*2);
}
for (int i = this.usedSize-1; i >= pos ; i--) {
this.array[i+1] = this.array[i];
}
this.array[pos] = data;
this.usedSize++;
}
//判断某元素是否存在
public boolean contains(int find){
for (int i = 0; i < this.usedSize; i++) {
if (this.array[i] == find){
return true;
}
}
return false;
}
//找到目标元素下标
public int indexOf(int find){
for (int i = 0; i < this.usedSize; i++) {
if (this.array[i] == find){
return i;
}
}
return -1;
}
//判断输入下标是否合法
public Boolean check(int pos){
if (pos < 0 || pos > this.usedSize - 1){
return false;
}
return true;
}
//获取pos位置的元素
public int get(int pos){
if (!check(pos)){
throw new exception(pos+"位置不合法");
}
return this.array[pos];
}
//将pos位置元素改为value
public void set(int pos,int value){
if (!check(pos)){
throw new exception(pos+"位置不合法");
}
this.array[pos] = value;
}
//删除第一次出现的目标元素
public void del(int toDel){
int dex = indexOf(toDel);
if (dex == -1){
System.out.println("没有要删除的元素");
return;
}
for (int i = dex; i < this.usedSize-1; i++) {
this.array[i] = this.array[i+1];
}
//引用类型
/*this.array[usedSize-1] = null;*/
this.usedSize--;
}
//获取顺序表长度
public int size(){
return this.usedSize;
}
//清空顺序表
public void clear(){
//引用类型
/*for (int i = 0; i < this.usedSize; i++) {
this.array[i] = null;
}*/
this.usedSize = 0;
}
}三.LinkedList(链表)
1.什么是线性表？
简介：
线性表 是n个具有 相同特性 的数据元素的有限序列，线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并 不一定是连续的空间 (如下图)
每个节点有两个域，一个存放 数据/值 (value)，一个存放 下一个节点的地址 (address)。通过上一个节点能够找到下一个节点，而且这些节点在物理结构上不一定是连续的，这就叫做线性表/链表。
2.链表的分类
从方向上来讲有三种类型
单向链表(如上图)：每个节点只有一个指向下一个节点的指针，最后一个节点的指针指向null。单向链表只能从头到尾进行遍历双向链表：每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。双向链表可以从任意一个节点开始，向前或向后进行遍历循环链表：链表的最后一个节点指向头节点，形成一个环。循环链表可以是单向的，也可以是双向的
从头节点的区别来讲有两个类型
带头链表：带头链表是指在链表的第一个节点之前增加一个特殊的节点，称为头结点。这个头结点通常不存储实际的数据，仅作为链表的起始点不带头链表(如上图)：链表中所有节点的结构是一致的，第一个节点是不确定的(后面讲到头插法就明白了)
通过以上排列组合，一共可以得到六种类型的链表
单向带头链表单向不带头链表双向带头链表双向不带头链表循环带头链表循环不带头链表
本文主要介绍 单向不带头链表 ，只要搞清楚这一个类型的原理，其他类型都是同理
3.单向不带头链表模拟实现
1.创建链表
2.求链表长度
3.头插法
4.尾插法
头插法不需要判断当前链表是否为空，但是尾插法需要
因为不论链表是否为空，头插法不会触发空指针异常；但当链表为空时，尾插法如果不进行判断，就会触发空指针异常
5.在pos位置添加元素
6.删除出现的第一个key目标
7.删除出现的所有key目标
8.清空链表
4.模拟实现的单向链表源码
public class MySingleList {
//内部类
static class ListNode{
public int val;
public ListNode next;
public ListNode(int val){
this.val = val;
}
}
//
private ListNode head;
//创建链表
public void createList(){
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
this.head = node1;
}
//打印链表
public void disPlay(){
ListNode cur = head;
if (head == null){
System.out.println("链表为空");
return;
}
while (cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//求链表长度
public int getSize(){
int count = 0;
ListNode cur = head;
while (cur != null){
cur = cur.next;
count++;
}
return count;
}
//查找key
public Boolean contains(int key){
ListNode cur = head;
while (cur != null){
if (cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
ListNode cur = head;
if (cur == null){
head = node;
return;
}
while (cur.next != null){
cur = cur.next;
}
cur.next = node;
}
//在pos位置添加元素,第一个节点下标为0,假如输入pos=2,那么该节点插入后就是链表的第2个节点
public void addPos(int pos,int data){
if (pos < 0 || pos > getSize()){
System.out.println("插入位置不合法");
return;
}
//pos == 0,直接使用头插法
if(pos == 0){
addFirst(data);
return;
}
//pos == getSize(),使用尾插法
if (pos == getSize()){
addLast(data);
return;
}
ListNode cur = toFindAddPosSubOne(pos);
ListNode node = new ListNode(data);
if (cur != null) {
node.next = cur.next;
cur.next = node;
}
}
//第一个节点下标为0,找到pos下标的前一个节点,并且返回该节点的地址
private ListNode toFindAddPosSubOne(int pos){
if (pos < 0 || pos > getSize()){
System.out.println("输入的位置不合法");
return null;
}
ListNode cur = head;
while ( pos - 1 != 0){
cur = cur.next;
pos--;
}
return cur;
}
//删除出现的第一个key目标
public void delFirstKey(int key){
if(head == null){
System.out.println("链表为空");
return;
}
if (head.val == key){
head = head.next;
}
ListNode cur = toFindDel(key);
if (cur == null){
System.out.println("没有你要删除的数字");
return;
}
cur.next = cur.next.next;
}
//找到要删除节点的前一个节点
private ListNode toFindDel(int key){
ListNode cur = head;
while (cur != null){
if (cur.next.val == key){
return cur;
}
cur = cur.next;
}
return null;
}
//删除出现的所有key目标
public void delAllKey(int key){
if(head == null){
System.out.println("链表为空");
return;
}
while (head.val == key){
head = head.next;
}
ListNode cur = head;
ListNode del = cur.next;
int count = 0;
while (del != null){
if (del.val != key){
del = del.next;
cur = cur.next;
}else {
cur.next = del.next;
del = del.next;
count++;
}
}
if (count == 0){
System.out.println("没有你要删除的数字");
}
}
//清空链表
public void clear(){
head = null;
}
}四.顺序表VS链表
存储方式
顺序表：使用连续的内存空间存储元素链表：使用非连续的内存空间存储元素
访问方式
顺序表：支持随机访问，通过下标/索引在O(1)时间内访问链表：不支持随机访问，通过遍历链表访问元素(O(n)时间复杂度)
删除和插入
顺序表：需要移动大量元素，例如：删除下标为2的元素，后面的元素都需要向前覆盖链表：头插法/尾插法，删除头/尾节点时间复杂度是O(1),虽然其他位置的插入和删除时间复杂度也是O(n)，但不需要大量地移动元素
容量
顺序表：自动扩容链表：没有容量这个概念
适用场景
顺序表：元素高效存储+频繁访问链表：任意位置插入和删除频繁