JAVA的线性表数据结构的超详解
目录
顺序表的顺序存储结构
1.数组
2.顺序表
顺序表的声明，存储操作以及效率分析
1.泛型类
2.顺序表的插入操作
3. 顺序表的删除操作
4.顺序表查询操作
5.顺序表的应用
线性表的链式存储结构
单链表的基本操作
顺序表的顺序存储结构
数组是实现顺序存储结构的基础
1.数组
程序设计语言中，数组（Array）具有相同数据类型，是一个构造数据类型。
一维数组占用一块内存空间，每个存储单元的地址是连续的，数据的存储单位个数称为数组容量。设数组变量为a，第i个元素（存储单元）为a[i],其中序号i称为下标，一维数组使用一个下标唯一确定一个元素。
如果数据存储结构存取任何一个元素的时间复杂度是O(1)，则称其为随机存储结构。因此，数组是随机存储结构。
数组一旦占用一片存储空间，其地址和容量就是确定的，不能更改。因此，数组只能进行赋值，取值两种操作，不能进行插入和删除操作。当数组容量不够时，不能就地扩容。
2.顺序表
线性表的顺序存储结构称为顺序表，它使用一维数组一次存放线性表的数据，且顺序表的性质和数组是一样的，因为顺序表的底层就是用数组来实现的。
顺序表的表现特点：
- 随机访问，可以在O(1)时间内找到第i个元素
- 存储密度高，每个节点只存储数据元素
- 扩展容量不方便（即便采用动态分配的方式实现，扩展长度的时间复杂度也比较高）
- 插入和删除操作不方便，需要移动大量元素
顺序表的声明，存储操作以及效率分析
1.泛型类
声明SeqList为泛型类，类型形式参数称为泛型，T表示顺序表数据元素的数据类型。
JAVA语言约定。泛型的实际参数必须是类，不能是int，char等基本数据类型。如果需要表示基本数据类型，也必须采用基本数据类型的包装类，如Integer，Character等等。
2.顺序表的插入操作
public class SequentialList{
private int[] array;//用于顺序表的数组
private int size;//顺序表的实际长度
public SequentialList(int capacity){
array =new int[capacity];
size=0;
}
//插入操作
public boolean insert(int index,int element){
//检查索引是否合法
if (indexsize){
System.out.println("插入的位置不合法");
return false;
}
//如果数组已满，则无法插入
if (size==array.length){
System.out.println("顺序表已满，无法插入");
return false;
}
//从插入位置开始，所有的元素向后移动一位
for (int i =size;i>index;i--){
array[i]=array[i-1];
}
//插入元素
array[index]=element;
//更新顺序表的长度
size++;
return true;
}
public void printList(){
for (int i = 0; i
3. 顺序表的删除操作
对顺序表进行插入和删除操作时，算法所花费的时间主要用于移动元素。若插入或删除在最前面，则需要移动n个元素；若插入或删除元素在最后，则移动元素为0。设插入x作为第i个元素的概率为p，插入一个元素的平均移动到次数为O（n）。
4.顺序表查询操作
根据查找条件，对顺序表进行查找操作，采用顺序查找算法，在查找过程中，需要将key与顺序表顺序表元素逐个比较是否相等。而比较对象对象相等规则有原数所属的T类的equals（Object）方法实现。
public int search(T key){
for(int i =0;i0;从start开始技术，0next
6） 将 q 结点中的数据赋值给 e, 作为返回
7） 释放 q 结点
8） 返回成功
// 删除特定值的节点
public void delete(int val) {
if (head == null) {
return;
}
if (head.val == val) {
head = head.next;
} else {
ListNode curr = head;
while (curr.next != null && curr.next.val != val) {
curr = curr.next;
}
if (curr.next != null) {
如果循环结束后，curr.next 不为 null，
说明找到了一个值等于 val 的节点。
这时，将 curr.next 更新为 curr.next.next
这样就将值等于 val 的节点从链表中删除了。
curr.next = curr.next.next;
}
}
}
3.查找倒数第k个元素
class LinkedList{
ListNode head;//链表的头节点
//查找倒数第k个元素
public ListNode findKthFromEndUsingTwoPasses(ListNode head,int k ){
//第一次遍历，计算链表的长度
int length =0;
ListNode current =head;
while(current!=null){
length++;
current=current.next;
}
//如果k大于链表长度，则不存在倒数第k个元素
if (k>length){
throw new IllegalArgumentException("k的值大于链表长度");
}
//第二次遍历，找到第length-k个节点
int index =0;
current =head;
while(current!=null&&index
