1、线性表的顺序存储-- 顺序表 （使用数组）
用一组
地址连续的存储单元依次存储线性表中每个数据元素，这种存储结构称为线性表的顺序存储结构，用这种结构表示的线性表称为
顺序表
java的顺序表：比如ArrayList类，用于查找，存储的频繁操作！
{
public class ArrayList<E>
{
private Object[] data =
null;
//data 用来保存此线性表的数据域
private int length;
//线性表的容量
private int current;
//实际表长
/**
* 查找下标返回元素值 快
* @param index
* @return
*/
public E get(int index){
if(index >= 0){
return (E) data[index];
}else {
throw new RuntimeException("下标不能小于0:" + index);
}
} /**
* 存储元素,添加之前判断线性表是否已经满了 慢
* @param e 添加的元素
* @return 成功返回真
*/
public boolean add(E e){
//判断是否已满
if(current >=
length){
length *= 2;
//将表最大容量*2
data = Arrays.copyOf(data, length);
//将原数组进行拷贝
} //将元素添加到数组末尾 this.data[current++] =
e; // ++current; //下标++ return true; }
顺序表的删除和插入两者的时间复杂度都是O(n)
优点
逻辑相邻，物理相邻
可随机存取任一元素
存储空间使用紧凑
缺点
插入、删除操作需要移动大量的元素
预先分配空间需按最大空间分配，利用不充分
表容量难以扩充
---------------------用处：用于查找，存储的频繁操作！
}
2、 线性表的链式存储-- 链表 （使用指针表示）
用一组地址任意的存储单元，通过结点的指针链接存储数据成的一个链表
每个存储单元叫做
结点 [ 数据域，指针域]
指针域 [
存放后继结点的地址]
链表{
java中的链表：
LinkedList ;插入删除快，查找慢！
单链表：{
private class Node{ //结点：数据、指针（下一个结点地址：java就是下一个类） private Object data; //数据 private Data next = null; //指针 Data(Object data){ this.data = data; } }
Node first =null;
//从前面插入
public void insertFisrt(Object obj){ Data data = new Data(obj); //新的数据 data.next = first; first = data } java图{ } private int pos = 0;
private int pos =0;
public void add(int index, int data) {
Node current = first;
while ( pos+1 != index-1) { //找到index位置前面一个Node
current= current.next;
pos++;
}
Node node = new Node(data);
node.next = current.next; //把新数据的next存储b
current.next = node; //把a数据里的next替换为c
pos = 0;
}
java图里{
}
线性表删除位置：要先找到前一个结点，然后待删除的结点设置为空，删除结点的下一个结点设置为上上个结点的值
public void delete(int index){
Node del;
Node per;
int pos = 0;
while(node!=null){
if(pos+1==index-1){
per = node
del = node.next;
}
pos++;
}
per.next = del.next;
del = null;
}
循环链表
：
{
private class LinkList{
createCruclarList(){
Node head = new Node(data);
head.next = head;
}
}
链表中的最后一个结点不是为空，而是指向第一个结点 也即是头结点，从而形成一个循环的链表。
所以一般运用在一个循环的链表中 一般最后结合双向链表进行运用
双向链表：
{
private class DNode{
int data;
DNode pre=null;
DNode next=null;
DNode(int data){
this.data = data;
}
}
private class LinkList{
p.next.per == p == p.per.next
|---------|------|---------|
p.per p p.next
}
每个结点中既有前驱结点，又有后继结点
}
//运用的比较多的一个
双向循环链表{
可以双向有有循环的链表
}
--------------- 用处：
用于插入，删除频繁的操作！
----------------操作算法较复杂，不能随机存储，需要额外的空间来存储空间，空间代价比较高。
