线性表（linear list）是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串。
用一段物理地址连续的存储单元依次存储数据元素的线性结构（逻辑上连续，物理上也连续）
（1）静态顺序表：使用定长数组存储。
（2）动态顺序表：使用动态开辟的数组存储
【注意】静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，所以相比之下，动态数组更为灵活，可根据需要动态分配空间大小
增、删、改、查
增加操作：从头部插入、从尾部插入、在任意索引位置处插入
删除操作：根据索引删除元素、根据元素值删除第一个出现的该元素、根据元素值删除所有该值元素
查找操作：根据元素值查找是否存在某元素、根据索引下标返回该处元素值、根据元素值返回索引下标
修改操作：根据索引下标修改该处元素
public class MyArray {
private int[]data;
private int size;
// 无参构造
public MyArray(){
this.data=new int[5];
}
// 有参构造
public MyArray(int n){
this.data=new int[n];
}
// grow方法用于扩充内存
private void grow() {
int[] newdata= Arrays.copyOf(data,size*2);
this.data=newdata;
}
// toString方法输出顺序表内容
public String toString(){
String str="[";
for (int i = 0; i <size ; i++) {
str+=data[i];
if(i!=size-1){
str+=",";
}
}
str+="]";
return str;
}
// 尾插法：
public void addLast(int value){
if(size== data.length){
grow();
}
data[size]=value;
size++;
}
// 头插法：
public void addFirst(int value){
if(size==data.length){
grow();
}
for (int i = size-1; i >=0; i--) {
data[i+1]=data[i];
}
data[0]=value;
size++;
}
// 中间任意位置插入：
public void addIndex(int index,int value){
if(size==data.length)
grow();
if(index<0||index>size){
System.err.println("插入位置不合理！");
return;
}
else {
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = value;
size++;
}
}
// 查看当前数组中是否存在该元素
public boolean contains(int value){
for (int i = 0; i < size; i++) {
if(data[i]==value)
return true;
}
return false;
}
// 查找当前数组元素对应的下标
public int getIndex(int value){
for (int i = 0; i < size; i++) {
if(data[i]==value){
return i;
}
}
return -1;
}
// 查找数组下标为index的元素
public int getValue(int index) {
if (index < 0 || index > size - 1) {
System.out.println("输入下标不合理");
return -1;
}
return data[index];
}
// 根据索引删除元素,注意将最后一个元素置为0
public void removeIndex(int index){
if(index<0||index>=size){
System.err.println("输入不合法！");
}
for (int i = index; i <size-1; i++) {
data[i]=data[i+1];
}
size--;
data[size]=0;
}
// 删除第一个元素值为value的元素
public void removeValueOnce(int value){
int a=getIndex(value);
removeIndex(a);
}
// 删除所有元素值为value的元素
public void removeValueAll(int value){
for (int i = 0; i < size; i++) {
while(i!=size||data[i]==value)
removeIndex(i);
}
}
// 根据索引修改元素
public void recompose(int index,int newValue){
if(index<0||index>=size){
System.err.println("输入不合法！");
}
data[index]=newValue;
}
}逻辑上连续，物理上非连续存储。
链表由一个个节点组成，每个节点存储该节点处的元素值val 以及下一个节点的地址next，由地址next实现逻辑上连续
分类方式：
（1）单链表、双链表
（2）带虚拟头节点、不带虚拟头节点
（3）循环链表、非循环链表
按不同分类方式组合有8种：
非循环四种：
（1）不带虚拟头节点的单向链表（非循环）
（2）带虚拟头节点的单向链表（非循环）
（3）不带虚拟头节点的双向链表（非循环）
（4）带虚拟头节点的双向链表（非循环）
循环四种：
（5）不带虚拟头节点的单向链表（循环）
（6）带虚拟头节点的单向链表（循环）
（7）不带虚拟头节点的双向链表（循环）
（8）带虚拟头节点的双向链表（循环）
其中：
（1）不带虚拟头节点的单向链表（非循环）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。这种结构在笔试面试中出现很多
（7）不带虚拟头节点的双向链表（循环）：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表
增、删、查、改 和顺序表实现方法基本一样；
唯一注意：带虚拟头节点与不带虚拟头节点相比，带虚拟头节点避免了考虑头节点为空的特殊情况
（1）不带虚拟头节点的单链表：
class Node {
// val表示存储的数值，next表示下一个节点的地址
int val;
Node next;
// 构造方法
public Node(int val) {
this.val = val;
}
}
public class SingleList {
// size表示节点个数
// head表示头节点
private int size;
private Node head;
//定义toString方法以输出链表内容
public String toString() {
String str = "";
Node node = head;
while (node != null) {
str += node.val;
str += "->";
node = node.next;
}
str += null;
return str;
}
//将判断输入的索引是否合法抽象为方法islegal
public boolean islegal(int index) {
if (index < 0 || index > size) {
return false;
} else {
return true;
}
}
// 头插法
public void addHead(int value) {
Node node = new Node(value);
if (head == null) {
head = node;
} else {
node.next = head;
head = node;
}
size++;
}
// 中间任意位置插入
public void addIndex(int index, int val) {
if (!islegal(index)) {
System.out.println("输入数据不合法！");
return;
}
if (index == 0) {
addHead(val);
return;
}
Node node = new Node(val);
Node pre = head;
for (int i = 0; i < index - 1; i++) {
pre = pre.next;
}
node.next = pre.next;
pre.next = node;
size++;
return;
}
// 尾插法
public void addLast(int val) {
if (head == null) {
addHead(val);
} else {
addIndex(size, val);
}
}
// 删除指定索引位置的元素
public void removeIndex(int index) {
if (islegal(index)) {
if (index == 0) {
Node temp = head;
head = head.next;
temp.next = null;
size--;
return;
} else {
Node pre = head;
for (int i = 0; i < index - 1; i++) {
pre = pre.next;
}
Node cur = pre.next;
pre.next = cur.next;
cur.next = null;
size--;
}
} else {
System.out.println("输入数据不合法！");
}
}
// 根据元素值删除元素，且只删除第一次出现的该元素
public void removeValueOnce(int val) {
if (head.next != null && head.val == val) {
removeIndex(0);
} else {
Node pre = head;
while (pre.next != null) {
if (pre.next.val == val) {
pre.next = pre.next.next;
pre.next.next = null;
size--;
return;
}
pre = pre.next;
}
}
}
// 根据元素值删除元素，且删除所有该元素
public void removeValueAll(int val) {
while (head.next != null && head.val == val) {
Node temp = head;
head = head.next;
temp = null;
size--;
}
if (head == null) {
return;
} else {
Node pre = head;
while (pre.next != null) {
if (pre.next.val == val) {
pre.next = pre.next.next;
size--;
return;
} else {
pre = pre.next;
}
}
}
}
// 根据元素值删除元素，且删除所有该元素并返回头节点(带虚假节点）
public Node removeValueAllWithDummy(int val) {
Node dummyHead = new Node(-1);
dummyHead.next = head;
Node pre = dummyHead;
while (pre.next != null) {
if (pre.next.val == val) {
Node cur = pre.next;
pre.next = cur.next;
cur.next = null;
size--;
} else {
pre = pre.next;
}
}
return dummyHead.next;
}
// 根据索引查元素值
public int get(int index) {
if (islegal(index)) {
Node cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
} else {
System.out.println("输入数据不合法！");
return -1;
}
}
// 能否查到给定的某元素值（自己写的，好像很复杂）
public boolean contains(int val) {
boolean a = false;
if (head == null) {
System.out.println("该链表为空！");
return false;
} else {
Node node = head;
for (int i = 0; i < size; i++) {
if (node.val == val) {
a = true;
}
node = node.next;
}
}
return a;
}
// 能否查到给定的某元素值，老师写的方法
public boolean contains2(int val) {
for (Node temp = head; temp != null; temp = temp.next) {
if (temp.val == val) {
return true;
}
}
return false;
}
// 根据索引修改元素值
public void set(int index, int newValue) {
if (islegal(index)) {
Node node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
node.val = newValue;
return;
}
System.out.println("输入数据不合法!");
}
}（2）带虚拟头节点的单链表
以在指定索引位置插入元素为例，理解虚拟头节点的作用即可
public class SingleListWithDummyHead {
Node dummyNode=new Node(-1);
int size;
// 在指定位置插入元素,因为有虚拟头节点故不用考虑index=0的情况，全部为在中间位置插入的情况
public void addIndex(int index,int value){
// 先判断index是否合法
if(index<0||index>size){
System.out.println("illegal");
return;
}
Node a=new Node(value);
Node pre=dummyNode;
for(int i=0;i<index;i++){
pre=pre.next;
}
a.next=pre.next;
pre.next=a;
size++;
}
}（3）带虚拟头节点的双链表
public class DoubleLinkedList {
private int size;
private Node dummyHead = new Node(-1);
private Node tail;
// 定义toString方法用以方便输出
public String toString() {
String s = "";
Node node = dummyHead.next;
while (node != null) {
s = s + node.val;
s = s + "->";
node = node.next;
}
s += "null";
return s;
}
// 判断输入的索引是否合法
private boolean isRange(int index) {
if (index < 0 || index >= size) {
System.out.println("输入不合法！");
return false;
} else
return true;
}
// 头插法
public void addHead(int val) {
Node a = new Node(val, dummyHead, dummyHead.next);
//链表为空
if (dummyHead.next == null) {
tail = a;
dummyHead.next = a;
}
// 否则链表不为空
else {
dummyHead.next.prev = a;
dummyHead.next = a;
}
size++;
}
// 尾插法
public void addTail(int val) {
Node a = new Node(val, tail, null);
// 链表为空
if (dummyHead.next == null) {
dummyHead.next = a;
}
// 链表不为空
else {
tail.next = a;
}
tail = a;
size++;
}
// 中间位置插入
public void addMiddle(int index, int val) {
// 判断插入位置合理否
if (index < 0 || index > size) {
System.out.println("输入不合法！");
}
// 头部插入
else if (index == 0) {
addHead(val);
}
// 尾部插入
else if (index == size) {
addTail(val);
}
// 中间任意位置插入
else {
//先找到要插入位置的前一个元素，可另一个方法找该元素
Node a = new Node(val, find(index), find(index).next);
find(index).next.prev = a;
find(index).next = a;
size++;
}
}
// 这里find的方法是找到index位置的前一个节点元素
public Node find(int index) {
Node f = dummyHead;
for (int i = 0; i < index; i++) {
f = f.next;
}
return f;
}
// 根据索引删除指定位置的元素
public void removeIndex(int index) {
if (index < 0 || index >= size) {
System.out.println("输入不合法!");
return;
} else {
find(index).next.next.prev = find(index);
find(index).next = find(index).next.next;
size--;
}
}
// 删除指定节点
private void deleteNode(Node node) {
// 分治思想，先处理node与左边节点，再处理node与右边节点
Node pre = node.prev;
Node next = node.next;
// 处理左边，因为有虚拟头节点，故不用另讨论为头节点的情况
pre.next = next;
node.prev = null;
// 处理右边
if (next == null) {
tail = pre;
} else {
next.prev = pre;
node.next = null;
}
size--;
}
// 删除指定元素值（只删除第一次出现的）
public void removeValueOnce(int val) {
for (Node a = dummyHead.next; a != null; a = a.next) {
if (a.val == val) {
deleteNode(a);
return;
}
}
System.out.println("链表中无该元素故无法删除");
}
public void removeValueAll(int val) {
for (Node a = dummyHead.next; a != null; ) {
if (a.val == val) {
Node b = a.next;
deleteNode(a);
a = b;
} else a = a.next;
}
}
// 根据索引查找元素值
public int get(int index) {
if (isRange(index)) {
return find(index).next.val;
} else {
return -1;
}
}
// 查找是否存在某元素
public boolean contains(int val) {
Node a = dummyHead;
while (a.next != null) {
if (a.next.val == val) {
return true;
}
a = a.next;
}
return false;
}
// 修改，将指定位置元素修改为另一值
public void set(int index, int newValue) {
if (isRange(index)) {
find(index).next.val = newValue;
}
}
}
//节点类
class Node {
int val;
Node prev;
Node next;
public Node(int val) {
this.val = val;
}
public Node(int val, Node prev, Node next) {
this.val = val;
this.prev = prev;
this.next = next;
}
}
顺序表：
优点：空间连续、支持随机访问
缺点：中间或前面部分的插入删除时间复杂度O(N)
增容的代价比较大。
链表：
优点：任意位置插入删除时间复杂度为O(1)
没有增容问题，插入一个开辟一个空间
缺点：以节点为单位存储，不支持随机访问
