目录
一、链表
二、单向链表
三、单链表的增删查改
一、单链表的增加
二，单链表的删除
三、单链表的修改
四、单链表的查找
四、双向链表
一、增加节点
二、.删除结点
三、链表的修改
四、链表的查询
一、链表
理解：链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
不像数组，相令邻的两个元素不仅逻辑上连续，物理上也连续。
可以把链表类比成火车，每一列火车由若干个车厢组成，每个车厢就是一个Node结点，由多个Node对象组成的大实体就是链表对象。火车的不同车厢之间，都是通过一个挂钩连接的，当这两个这厢脱钩后，这两个车厢就没有任何关系了。
二、单向链表
每个节点只保存了下一个节点的地址，只能从头节点开始向后遍历，这种链表结构称为单向链表简称单链表。
1.链表定义节点
class Node{
//存放结点的值
int val;
//存放下一结点地址
Node next;
public Node(int val) {
this.val = val;
}
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
2.不带头的单链表的创建
public class SingleLinedList {
//链表的头结点
private Node head=null;
//当前链表中Node节点的个数 = 有效数值的个数
private int size=0;
class Node{
//存放结点的值
int val;
//存放下一结点地址
Node next;
public Node(int val) {
this.val = val;
}
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
}
单链表的遍历
public String toString(){
//遍历链表
String ret="";
Node x=head;
while (x!=null){
ret+=x.val;
ret+="->";
x=x.next;
}
ret+="Null";
return ret;
}
从当前头节点开始，依次取出每个节点值，然后通过next引用走到下一个节点，直到走到链表的末尾(next = null)
遍历过程中，能否直接使用head引用?直接使用head引用，遍历一次链表之后，链表就丢了~~
三、单链表的增删查改
我们只需要调用单链表提供的增删改查方法即可，至于链表内部节点如何连接的，如何遍历的都不关心。
一、单链表的增加
1.头插
public void addFirst(int val){
Node newNode=new Node(val);
newNode.next = head; // 直接将该结点node变成新的头结点
head = newNode;
size++;
}
2.下标插入
public void addIndex(int index,int val) {
// 1.若index位置非法的
if(index<0 || index>size){
System.out.println("index is illegal");
return;
}
// 2.插入任意位置要找到前驱结点，但是链表中有一个结点没有前驱
// 头结点没有前驱！！！
if(index==0){
addFirst(val);
}else {
// 3.当前索引合法且不是在数组的头部插入,就要找到插入位置的前驱结点
Node prev=head;
Node newNode=new Node();
newNode.val=val;
for (int i = 0; i < index-1; i++) {
prev=prev.next;
}
// 此时prev一定指向了待插入节点的前驱
newNode.next=prev.next;
prev.next=newNode;
size++;
}
}
二，单链表的删除
remove(int index);
单链表的插入和删除，最核心的就是在找前驱结点，只能从前向后操作。
1.删除指定下标，返回删除前的元素
public int remove(int index){
if (index>=0 && index
2.删除链表中第一个值为val的元素
public void removeValueOnce(int val) {
//链表为空
if(head==null){
System.out.println("LinedList is empty");
return;
}
//要删除的是头结点
if(head.val==val){
Node x=head;
head=head.next;
x.next=null;
}else {
//找前驱结点
Node prev=head;
while (prev.next!=null){
//有后继结点
if(prev.next.val==val){
//此时后继结点就是要删除的结点
Node x=prev.next;
prev.next=x.next;
x.next=null;
return;
}
prev=prev.next;
}
}
size--;
}
三、单链表的修改
set(int index,int newVal);//修改索引为index位置的结点值为newVal
1.修改索引为index位置的结点值为newVal，返回修改前的节点值
public int set(int index,int newVal){
if(index>=0 && index
四、单链表的查找
boolean contains(int val);//是否包含指定值的结点
get(int index);/查询索引为index的元素值是多少。
getByValue(int val);//查询第一个值为val的结点索引是多少
1.查找第一个值为val的结点索引
public int getByValue(int val) {
int index=0;
Node pre=head;
while (pre.next!=null){
if(pre.next.val==val){
return index;
}
pre=pre.next;
index++;
}
// 说明当前链表中根本就没有值为val的结点，返回-1,表示不存在
return -1;
}
2.查找索引为index位置的结点值
public int get(int index) {
// 1.判断index的合法性
if(index>=0 && index
3.查找值为val的结点是否在链表中
public boolean contains(int val) {
int index = getByValue(val);
return index != -1;
}
四、双向链表
一、增加节点
1.头插
//头插法
public void addFirst(int val){
DoubleNode node=new DoubleNode(null,val,head);
//链表为空
if(tail==null){
tail=node;
}else {//链表不为空
head.prev=node;
}
// 对于头插来说，最终无论链表是否为空。head = node
head=node;
size++;
}
2.尾插
public void addLast(int val){
DoubleNode node=new DoubleNode(tail,val,null);
if(head==null){
head=node;
}else {
tail.next=node;
}
//尾插最终tail都会等于node
tail=node;
size++;
}
3.在index位置插入
假设我们现在有100个结点，在97号结点插入新元素，从尾结点向前遍历就会快很多,我们可以创建一个私有方法来根据索引找到结点
private DoubleNode node(int index){
//根据索引找到对应结点
DoubleNode x=null;
if(index<=size/2){
x=head;
for (int i = 0; i < index; i++) {
x=x.next;
}
}else {
x=tail;
for (int i=size-1; i>index; i--){
x=x.prev;
}
}
return x;
}
执行插入
public void add(int index,int val){
if(index < 0 || index > size){
System.out.println("index is illegal");
return;
}
if(index==0){
addFirst(val);
}else if (index==size){
addLast(val);
}else {
//中间位置插入
DoubleNode pre=node(index-1);
DoubleNode next=pre.next;
DoubleNode cur=new DoubleNode(pre,val,next);
next.prev=cur;
pre.next=cur;
size++;
}
}
二、.删除结点
先处理前驱节点的问题，前驱部分处理完毕再单独处理后继部分，我们创建一个私有方法，传入要删除的结点，将其从链表中删除
private void unlink(DoubleNode node){
//1.前空后不空
//2.前不空后空
//3.前后都为空
//4.前后都不空
DoubleNode pre=node.prev;
DoubleNode next=node.next;
//先处理前驱
if(pre==null){
//前驱为空，node为头结点
head=next;
}else {
pre.next=next;
node.prev=null;
}
//处理后继
if(next==null){
tail=pre;
}else {
next.prev=pre;
node.next=null;
}
size--;
}
指定下标删除,返回删除前的元素
public void removeIndex(int index){
if(index<0 || index>=size){
System.out.println("index is illegal");
return;
}
DoubleNode node=node(index);
unlink(node);
}
删除值为val的结点
public void removeOnce(int val){
DoubleNode x=head;
while (x!=null){
if(x.val==val){
unlink(x);
break;
}
x=x.next;
}
}
删除所有值为val的结点
public void removeAll(int val){
DoubleNode x=head;
while (x!=null){
if(x.val==val){
//暂存一下x后继结点的地址
DoubleNode next=x.next;
unlink(x);
x=next;
}else {
x=x.next;
}
}
}
三、链表的修改
修改index处的值为newVal，返回index
public int set(int index,int newVal) {
if(index<0 || index>=size){
System.out.println("index is illegal");
return -1;
}
DoubleNode node=node(index);
int oldVal=node.val;
node.val=newVal;
return oldVal;
}
四、链表的查询
1.查找索引为index位置的结点值
//获取index处结点的值
public int get(int index) {
if(index<0 || index>=size){
System.out.println("index is illegal");
return -1;
}
DoubleNode node=node(index);
int val=node.val;
return val;
}
