单链表
如果是null，就阐明前面没有节点了，如果不是null就阐明前面要连贯节点
每个节点蕴含2局部，数据域，和一个指向下一个节点援用的指针next
data域–寄存结点值的数据域
next域–寄存结点的间接后继的地址的指针域（链域）
链表通过每个结点的链域将线性表的n个结点按其逻辑程序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。
单链表
显示所有节点信息
- 头部插入节点
- 如果链表没有头结点，新结点间接成为头结点；否则新结点的next间接指向以后头结点，并让新结点成为新的头结点。
/**
* 增加结点至链表头部
*
* @param value
*/
public void addHeadNode(T value) {
Node newNode = new Node(value);
//头结点不存在，新结点成为头结点
if (head == null) {
head = newNode;
return;
}
//新结点next间接指向以后头结点
newNode.next = head;
//新结点成为新的头结点
head = newNode;
}- 尾部插入节点
- 如果链表没有头结点，新结点间接成为头结点；否则须要先找到链表以后的尾结点，并将新结点插入到链表尾部。
/**
* 增加结点至链表尾部
*
* @param value
*/
public void addTailNode(T value) {
Node newNode = new Node(value);
//头结点不存在，新结点成为头结点
if (head == null) {
head = newNode;
return;
}
//找到最初一个结点
Node last = head;
while (last.next != null) {
last = last.next;
}
//新结点插入到链表尾部
last.next = newNode;
}- 指定地位插入节点
- 先判断插入地位为头尾两端的状况，即index == 0插入到头部，index == size()插入到尾部；如果插入地位不是头尾两端，则先找出以后index地位的结点cur以及前一个结点 pre，而后cur成为新结点的下一个结点，新结点成为pre的后一个结点，这样就胜利插入到index地位。
/**
* 结点插入至指定地位
*
* @param value 结点数据
* @param index 插入地位
*/
public void addNodeAtIndex(T value, int index) {
if (index < 0 || index > size()) { //留神index是能够等于size()的
throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
}
if (index == 0) { //插入到头部
addHeadNode(value);//后面定义的办法
} else if (index == size()) { //插入到尾部
addTailNode(value);//后面定义的办法
} else { //插到某个两头地位
Node newNode = new Node(value);
int position = 0;
Node cur = head; //标记以后结点
Node pre = null; //记录前置结点
while (cur != null) {
if (position == index) {
newNode.next = cur;
pre.next = newNode;
return;
}
pre = cur;
cur = cur.next;
position++;
}
}
}插入一个节点做以后节点的下一个节点
- 指定地位删除节点
- 找出以后index地位的结点cur以及前一个结点 pre，pre.next间接指向cur.next即可删除cur结点。
/**
* 删除指定地位的结点
*
* @param index 指定地位
*/
public void deleteNodeAtIndex(int index) {
if (index < 0 || index > size() - 1) {
throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
}
if (index == 0) { //删除头
head = head.next;
return;
}
int position = 0; //记录以后地位
Node cur = head; //标记以后结点
Node pre = null; //记录前置结点
while (cur != null) {
if (position == index) {
pre.next = cur.next;
cur.next = null; //断开cur与链表的连贯
return;
}
pre = cur;
cur = cur.next;
position++;
}
}- 删除下一个节点
- 链表反转
- 在链表遍历的过程中将指针程序置换，即每遍历一次链表就让cur.next指向pre，最初一个结点成为新的头结点。反转之后指针入下图红线所示。
/**
* 链表反转
*/
public void reverse() {
Node cur = head; //标记以后结点
Node pre = null; //标记以后结点的前一个结点
Node temp;
while (cur != null) {
//保留以后结点的下一个结点
temp = cur.next;
//cur.next指向pre，指针程序置换
cur.next = pre;
//pre、cur持续后移
pre = cur;
cur = temp;
}
//最初一个结点变成新的头结点
head = pre;
}- 求倒数第k个结点
- 倒数第k个结点就是第size() – k + 1个结点，cur结点向后挪动size() – k次就是倒数第k个结点。
/**
* 倒数第k个结点
*
* @param k
* @return
*/
public T getLastK(int k) {
if (k < 0 || k > size()) { //留神index是能够等于size()的
throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
}
Node cur = head;
for (int i = 1; i < size() - k + 1; i++) {
cur = cur.next;
}
return cur.value;
}循环链表
循环链表
双链表
双向链表
循环双向列表
循环双向列表一开始的pre和next都是本人
发表回复