3，链表
链表是一种以结点的形式存储数据的结构，而结点通常由数据域（data）和指针域（next）组成,分别用于存放数据和指向下一个结点位置。
常见的，有单链表、双链表、循环链表。
链表通常有带头结点和不带头结点两种。
为什么需要头结点？
没有头结点时，在最前面插入删除需要修改表头指针,在其他位置插入删除时修改前驱结点的next域，两种操作需要分别处理。因此为了操作统一，我们一般使用一个虚拟的头结点，它本身不存储数据。
3.1，单链表
单链表定义：
public class Node{
T data;
Node next;
}
单链表实现及基本操作：
基本构成：
- 结点定义
- 构造方法
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：
- addAtTail(val)：
- addAtIndex(index,val)：
- deleteAtIndex(index)：
/**结点定义*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class MyLinkedList {
int size;
ListNode head;
/** Initialize your data structure here. */
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
/** 获得指定位置的结点的值. */
public int get(int index) {
if(index<0 || index>=size)return -1;
ListNode curr = head;
// 链表只能一步步移动到指定位置
for(int i=0;i<index+1;++i){
curr = curr.next;
}
return curr.val;
}
/**将元素插入头结点*/
public void addAtHead(int val) {
addAtIndex(0,val);
}
/**将元素插入尾结点*/
public void addAtTail(int val) {
addAtIndex(size,val);
}
/**在指定索引处插入元素*/
public void addAtIndex(int index, int val) {
if(index>size) return; //大于size不会插入，直接退出
if(index<0){ //小于0，在头部插入
index = 0;
}
//等于链表长度，在尾部（index=size）插入；在size范围内，在index出插入
++size;
// 插入位置的前一个节点
ListNode pred = head;
// 移动到插入位置
for(int i =0;i<index;++i){
pred = pred.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
/** 删除指定索引的结点 */
public void deleteAtIndex(int index) {
if(index<0 || index>=size)return ;
size--;
ListNode pred = head;
for(int i =0;i<index;++i){
pred = pred.next;
}
pred.next = pred.next.next;
}
}
3.2，双链表
双向链表能够解决单向链表只能单方向进行操作的弊端。牺牲了存储空间，提升了操作速度。
双链表定义：
public class Node{
T data;
Node pre;
Node next;
}
双链表实现即基本操作：
public class ListNode{
int val;
ListNode prev;
ListNode next;
ListNode(int x){
val = x;
}
}
class MyLinkedList{
int size;
ListNode head,tail; //设置一个头结点和一个尾结点
public MyLinkedList(){
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
public int get(int index){
if(index < 0 || index>=size) return -1;
ListNode curr = head;
//根据位置选择是从头还是尾部开始查找
if(index+1 < size-index){
for(int i = 0;i<index+1;++i) curr = curr.next;
}else{
curr = tail;
for(int i = 0;i<size-index;++i) curr = curr.prev;
}
return curr.val;
}
public void addAtHead(int val){
ListNode pred = head,succ = head.next;
++size;
ListNode toAdd = new ListNode(val);
toAdd.prev = pred;
toAdd.next = succ;
pred.next = toAdd;
succ.prev = toAdd;
}
public void addAtTail(int val){
ListNode succ = tail,pred = tail.prev;
++size;
ListNode toAdd = new ListNode(val);
toAdd.prev = pred;
toAdd.next = succ;
pred.next = toAdd;
succ.prev = toAdd;
}
public void addAtIndex(int index,int val){
if(index>size) return;
if(index<0) index = 0;
ListNode pred,succ;
if(index<size-index){
pred = head;
for(int i = 0;i<index;++i)pred = pred.next;
succ = pred.next;
}else{
succ = tail;
for(int i = 0;i<size-index;++i)succ = succ.prev;
pred = succ.prev;
}
++size;
ListNode toAdd = new ListNode(val);
toAdd.prev = pred;
toAdd.next = succ;
pred.next = toAdd;
succ.prev = toAdd;
}
public void deleteAtIndex(int index){
if(index<0 || index>=size) return;
ListNode pred,succ;
if(index<size-index){
pred = head;
for(int i = 0;i<index;++i)pred = pred.next;
succ = pred.next.next;
}else{
succ = tail;
for(int i = 0;i<size-index-1;++i)succ = succ.prev;
pred = succ.prev.prev;
}
--size;
pred.next = succ;
succ.prev = pred;
}
}
3.3，循环链表
循环单链表，循环双链表