线性表是我们日常中用到的最多的数据结构，它的最基本的特点是它最多只有一个前驱，最多只有一个后驱，只有第一个节点没有前驱，只有最后一个节点没有后驱。
简言之：线性表就是n 个元素的有限序列，其一般描述为
A = (a1,a2,a3…)
线性表的存储结构分为：顺序存储和非顺序存储，其中顺序存储又叫向量存储，也叫一维数组存储。
1.顺序存储
线性表的顺序存储也叫向量存储，也叫一维数组存储。线性表中节点存放的物理顺序 和逻辑顺序是一样的，A = (a1,a2,a3…)对应的存储结构图如下：
线性表中第一个元素的位置通常称为起始位置或者基地址，表中相邻两个元素之间据有相邻的存储位置。
顺序存储结构的线性表据有随机访问的特点，如java中的数组，可以通过下标随机的访问该下标位置的元素，但是对 数组元素进行增删就比较麻烦，因为是顺序存储的，增加或删除需要移动之后 的数据。
2.链式存储结构
链式存储结构在 java数据结构中的应用为链表
java代码实现链表可浏览另一篇博客：代码实现链表
- 单向链表
对于 链式存储 结构线性表，其存储时的任意数据特点 形式都如下：
其中data是数据域，存放的具体内容，next为指针域，指向下一节点的地址。单项链表只有后驱，双向链表有前驱和后驱。
链表的增加和删除数据只需该表指针的指向即可。
单链表的插入操作图示如下：
单链表的删除操作图示如下：
注意：删除节点只是将节点在链表中删除，该节点还存在，所以不能丢失被删除节点的内存，还需要将节点保留返还给空闲的寄存器。为了将删除节点返回 ，需要将被删除节点的指针赋给临时的指针。
3.循环链表
循环链表的结构基本等同与单向链表，只是链表的最后一节点的next指针指向了头节点，形成了一个环路。
4.双向链表
在单向链表中，虽然从任意已知节点能够找到他的直接 前驱节点，但是需要从第一节点开始做循环操作，时间复杂度为
所以双向链表能够解决这一问题，它提供一个前驱指针，指向上一节点，能够快速的知道它的前驱节点。
双向链表的节点结构图如下：
java代码实现链表可浏览另一篇博客：代码实现链表
代码实现链表的反转：递归和循环
public class ListNodeTest {
private static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
public String show() {
return this.val + "->" + (this.next == null ? "NULL" : this.next.show());
}
}
/**
* 迭代
*/
public ListNode reverseList2(ListNode head) {
ListNode pre = null; //存上一个节点
while (head != null) {
ListNode current = head;
head = head.next;
current.next = pre;
pre = current;
}
return pre;
}
/**
* 递归
*/
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode nextNode = head.next;
ListNode newHead = reverseList(nextNode);
nextNode.next = head;
head.next = null;
return newHead;
}
@Test
public void testReverse() {
ListNode a = new ListNode(1);
ListNode b = new ListNode(2);
ListNode c = new ListNode(3);
ListNode d = new ListNode(4);
a.next = b;
b.next = c;
c.next = d;
System.out.println(a.show());
System.out.println(reverseList2(a).show());
}
}
