基本概念
线性表：有n(n>=0)个相同数据类型数据元素组成的
线性结构。其实现方法见图。
线性结构：除了第一个和最后一个数据元素，其余各元素只有一个前驱元素和后继元素，第一个数据元素只有一个后继元素，最后一个数据元素只有一个前驱元素。其分类见图。
顺序存储结构：数据元素存储在一块连续的地址空间中，数据元素间的逻辑关系表现在连续的地址空间上，逻辑上相邻的数据元素在物理上也相邻。
链式存储结构：存储数据元素的空间并不连续，数据元素间的逻辑关系用指针来实现，逻辑上相邻的数据元素在物理上不一定相邻。
顺序表：采用顺序存储结构的线性表。
链表：采用链式存储结构的线性表。可分为：单链表、单循环链表、双向循环链表。
说下第二张图中的
堆栈和
队列：
- 堆栈：是一种特殊的线性表，它只允许在线性表的表头进行删除和插入操作。
- 队列：也是一种特殊的线性表，它只允许在线性表的表头进行删除操作，而在表尾进行插入操作。
下面说下
顺序表、
仿真链表和
链表的区别：
其实就是各自保存数据元素间关系的方法不一样。
- 顺序表：数据元素的关系表现在连续的地址空间上；
- 仿真链表：通过保存数据元素在数组中存放的下标来保存数据元素间的关系；
- 链表：通过保存数据元素在内存中的存放地址（或者引用）来保存数据元素间的关系。
头结点：不存放数据元素的第一个结点；
头指针：指向头结点的指针。
带头结点与不带头结点的区别：
- 带头结点：插入第一结点和非第一个结点时，其操作都一样的；
- 不带头结点：当插入第一个结点时，需要单独考虑哈。删除结点时，两者的区别与插入结点时类似。
代码实现
结点类：
public class Node{
private Object data;
private Node next;
//如果new时，采用 new Node(null)，则得到一个没有存储数据的结点，即：头结点。
public Node(Object data){
this.data = data;
}
public void setData(Object data){
this.data = data;
}
public void setNext(Next next){
this.next = next;
}
public Object getData(){
return this.data;
}
public Node getNext(){
return this.next;
}
}public class HeadLinkList{
private Node head;
private int currentSize;
public HeadList(){
head = new Node(null); //构造一个未存放数据的头结点。
currentSize = 1;
}
//返回下标为 i 的那个结点的指针
public Node index(int i){ //结点编号从0开始，头结点下标为0；
if(i>=0 && i< currentSize ){
Node temp = head;
for(int j = 0 ; j < i;j++){
temp = temp.getNext();
}
return temp;
}else{
throw new Exception("下标超界！");
}
}
//插入结点，使其成为第 i 个结点。
public void insertNode(Node node,int i){
Node temp = index(i-1);
node.setNext(temp.getNext());
temp.setNext(node);
currentSize++;
}
//删除编号为 i 的结点
public void deleteNode(int i){
Node temp = index(i-1);
temp.setNext(temp.getNext().getNext());
}
//getter setter
}不带头结点的单链表类：
public class NoHeadLinkList{
private Node head;
private int currentSize;
public HeadList(){
head = null;
currentSize = 0;
}
//返回下标为 i 的那个结点的指针
public Node index(int i){ //结点编号从0开始；
if(i>=0 && i< currentSize ){
Node temp = head;
for(int j = 0 ; j < i;j++){
temp = temp.getNext();
}
return temp;
}else{
throw new Exception("下标超界！");
}
}
//插入结点，使其成为第 i 个结点。
public void insertNode(Node node,int i){
if(head == null){
head = node;
currentSize++;
}else{
Node temp = index(i-1);
node.setNext(temp.getNext());
temp.setNext(node);
currentSize++;
}
}
//删除编号为 i 的结点
public void deleteNode(int i){
if(i == 0){
Node temp = index(0);
head = temp.getNext();
temp.setNext(null);
}else{
Node temp = index(i-1);
temp.setNext(temp.getNext().getNext());
}
}
//getter setter
}
持续更新中。。。。。
