- 一、链表的概念
- 二、创建链表
- 新增节点
- 删除节点
- 查询链表节点
- 修改链表节点
- 三、双向链表
- 定义节点
- 新增节点
- 删除节点
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
可以把单链表类比为火车，火车的不同车厢之间，都是通过一个挂钩连接的，当这两个车厢脱钩后就没有任何关系了，不像我们的数组，相邻的两个元素不仅逻辑上连续，物理也连续。
假设咱们现在每节火车车厢只保存一个int值，这个值就是我们要存储的数据，每个车厢还要保存下一个车厢的地址。
单相链表：每个节点只保存了下一个节点的地址，只能从头节点开始向后遍历，这种链表结构称为单向链表，简称单链表。
节点类如何定义？->每节火车车厢
class Node{
int val;
//存放节点的值
Node next;
//存放下一节点的地址
public Node(){};
public Node(int val){
this.val = val;
}
public Node(int val,Node next){
this.val = val;
this.next = next;
}
}
链表有很多种类，我们先介绍单链表，
二、创建链表给你一个火车头，Node head；就可以遍历当前链表中所有的节点，从head开始向后遍历。
public class SingleLineList {
//链表的头结点
private Node head = null;
//当前链表中Node节点的个数 = 有效值的个数
private int size = 0;
这样我们就创建好了一个基本的链表结构。
我们先重写一下toString方法，遍历链表，实现链表的打印操作。
//toString方法
public String toString(){
String ret = "";
for(Node x = dummyHead.next;x!=null;x=x.next){
ret += x.val;
ret += "->";
}
ret += "NULL";
return ret;
}
那么我们下面就开始创建链表
新增节点- 头插
public void addFirst(int val){
Node newNode = new Node();
//保存值
newNode.val = val;
if (head == null){
//newNode就是第一个节点
head =newNode;
}
else {
//当前火车不为空
newNode.next = head;
head = newNode;
}
size ++;
}
- 从指定下标插入
想要在index位置插入新节点，因为单链表只可以从后向前遍历，我们只需要找到要插入节点的前驱结点。我们可以让prev引用从头结点开始走index-1步，这样就找到了待插入结点的前驱结点
public void add(int index,int val){
//1.若index位置非法的
if(index<0||index>size){
System.out.println("add index error");
return;
}
if (index==0){
addFirst(val);
}
else {
//3.当前索引合法且不是在数组的头部插入，就要找到插入位置的钱去
Node newNode = new Node();
newNode.val = val;
Node prev = head;
for (int i =0;i
prev = prev.next;
}
newNode.next = prev.next;
prev.next = newNode;
size++;
}
}
- 尾插
//在链表尾部插入节点
public void addLast(int val){
add(size,val);
}
删除节点
删除一个节点，是将一个节点从当前链表中分离出来，如果我们想删除下标为1的节点，只需要找到他的前一个节点，即下标为0的，然后将他的next指向删除节点的后一个节点，并且断开该节点与前后节点的连接。这样该节点就会被删除
- 删除链表中索引为index位置的节点，返回删除前节点的值
public int remove(int index){
//判断索引的合法性
if (index<0||index>size){
System.out.println("index is error");
return -1;
}
//判断删除位置是不是头结点
if (index == 0){
Node x = head;
head = head.next;//头结点的下一个节点为头结点
size--;
x.next = null;//断开头结点的指向
return x.val;
}
else{
//此时删除的是链表的中间节点
//找前驱
Node prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
//此时prev就是当前待删除结点的前驱
//node结点就是待删除的结点
Node node = prev.next;
prev.next = node.next;
node.next = null;
size --;
return node.val;
}
}
- 删除链表中第一次出现的值为val的节点
public void removeValueOnce(int val){
if (head == null){
System.out.println("链表为空无法删除");
return ;
}
if (head.val==val){
Node x = head;
head = head.next;
x.next = null;
size --;
}
else {
//当前头结点不是待删除的结点，需要遍历
//这里同样找到待删除的前驱结点
//能否知道前驱结点移动步数
Node prev = head;
while (prev.next!=null){
//至少还有后继节点
if (prev.next.val==val){
//此时prev.next.val == val
Node node = prev.next;
prev.next = node.next;
node.next = null;
size--;
return;
}
prev = prev.next;
}
}
}
- 删除全部值为val的节点
public void removeAllValue(int val){
while (head!=null&&head.val==val){
//头结点就是待删除结点
Node x = head;
head = head.next;
x.next = null;
size--;
}
//头结点一定不是待删除结点
//判空
if (head==null){
System.out.println("链表为空");
}
else{
Node prev = head;
while (prev.next!=null){
if (prev.next.val==val){
Node node = prev.next;
prev.next = node.next;
node.next = null;
size --;
}else {
prev = prev.next;
}
}
}
}
- 查询索引为index位置的节点
public int get(int index){
if (index<0||index>size){
System.out.println("get is error");
return -1;
}
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x.val;
}
- 查询第一个为val的节点
public int getByValue(int val){
int index = 0;
for (Node x = head;x!=null;x = x.next){
if (x.val==val){
return index;
}
index ++;
}
//说明当前链表中根本没有值为val的结点，返回-1，表示不存在
return -1;
}
//判断是否有这个值
public boolean contains(int val){
// int index = getByValue(val);
// return index!=-1;
for (Node x=head;x!=null;x=x.next){
if (x.val==val){
return true;
}
}
return false;
}
修改链表节点
public int set(int index,int newVal){
if (index<0||index>size){
System.out.println("get is error");
return -1;
}
//找到索引位置
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
// 修改索引位置的元素
int oldVal = x.val;
x.val = newVal;
return oldVal;
}
三、双向链表
单链表：单向链表，默认只能从链表的头部遍历到链表的尾部，实际的引用中很少见，太局限，只能从头遍历到尾部。
双向链表：对于该链表中的任意节点，即可通过该节点向后走，也可以通过该节点向前走。
双向链表实际工程中应用非常广泛，使用链表这个结构的首选。
定义节点//双向链表的节点类
class DoubleNode{
//前驱结点
DoubleNode prev;
//当前结点值
int val;
//后继节点
DoubleNode next;
public DoubleNode(){}
public DoubleNode(int val){
this.val = val;
}
public DoubleNode(DoubleNode prev,int val,DoubleNode next){
this.next = next;
this.prev = prev;
this.val = val;
}
}
public class DoubleLinkList {
//有效节点的个数
private int size;
//当前头结点
private DoubleNode head;
//当前尾结点
private DoubleNode tail;
}
新增节点
- 头插法
//在双向链表的头部插入一个新节点
public void addFirst(int val) {
//首先创建一个节点
DoubleNode node = new DoubleNode(val);
if (head == null) {
head = tail = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
size++;
}
- 尾插法
public void addLast(int val){
DoubleNode node = new DoubleNode(tail,val,null);
if (tail == null){
head = node;
}
else{
tail.next = node;
}
tail = node;
size++;
}
- 在索引index处插入新元素val
public void add(int index,int val){
//边界条件
if (index<0||index>size){
System.out.println("add index illegal");
return;
}
if (index==0) {
addFirst(val);
}
else if (index==size) {
addLast(val);
}
else{
//中间节点插入
DoubleNode prev = node(index-1);
DoubleNode next = prev.next;
DoubleNode cur = new DoubleNode(prev,val,next);
prev.next = cur;
next.prev = cur;
size++;
}
}
删除节点
这里运用分治思想：
先处理前驱结点的事儿，完全不管后继。
等前驱部分全部处理完毕在单独处理后继情况
private void unlink(DoubleNode node){
//1.前空后不空
//2.前不空后空
//3.前不空后不空
//4.前空后不空
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先处理node的前半部分
if (prev==null){
head = successor;
}
else {
//前驱不为空的情况
prev.next = successor;
node.prev = null;
}
//2.再处理node的后半部分
if (successor==null){
tail = prev;
}
else {
successor.prev = prev;
node.next = null;
}
size --;
}
- 删除索引为index的结点
public void removeIndex(int index){
if (index<0||index>=size){
System.out.println("remove index illegal!");
return;
}
DoubleNode cur = node(index);
unlink(cur);
}
- 删除第一次值为val的节点
public void removeValueOnce(int val){
for (DoubleNode x = head;x!=null;x = x.next){
if (x.val == val){
unlink(x);
//x.next就断开了
break;
}
}
}
- 删除所有值为val的节点
public void removeAllValue(int val){
for (DoubleNode x = head;x != null;){
if (x.val == val) {
// x就是待删除的结点
// 暂存后继结点的地址
DoubleNode successor = x.next;
unlink(x);
x = successor;
}else {
x = x.next;
}
}
}
- 删除首节点和尾节点
public void removeFirst(){
removeIndex(0);
}
public void removeLast(){
removeIndex(size-1);
}
