- 无头双向链表
- 双向链表的概念及结构
- 链表的实现
- 打印双链表
- 获取双链表的长度
- 查找是否包含关键字key是否在双链表中
- 头插法
- 尾插法
- 任意位置插入,第一个数据节点为0号下标
- 删除第一次出现关键字为key的节点
- 删除所有值为key的节点
- 置空链表
【前言】在前面的文章中我们已经对顺序表和单链表的基本功能有了一些了解，那么接下来就让我们一起来学习一下双向链表的基本功能是如何实现的。首先让我们先看一下双向链表的结构：
无头双向链表 双向链表的概念及结构
概念： 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
结构：
在我们实现链表的接口功能前，我们要先创建两个类，链表类（包含有一个可变的头结点和可变的尾结点及实现各种功能的接口）和节点类（包含成员属性value，prev前驱和next后继）。
class ListNode{
public int value;//数据域
public ListNode prev;//前驱
public ListNode next;//后继
public ListNode(int value){
this.value= value;
}
}
public class linkList {
public ListNode head;//定义链表的头引用
public ListNode last;//定义链表的尾巴节点
}
打印双链表
它的思想和打印顺序表思想类似，遍历链表即可，但是需要注意的是： 需要创建一个局部变量cur来代替头结点去遍历，因为头结点在没添加或删除节点之前是固定的，不能让它变来变去的。
public void disply(){
ListNode cur=this.head;//引用变量cur代替头结点
while(cur!=null){//当节点不为空时遍历单链表，节点为空说明遍历结束
System.out.print(cur.value+" ");
cur=cur.next;//指向下一个节点
}
System.out.println();
}
获取双链表的长度
引用局部变量cur来遍历链表，并引用一个局部变量count来计数，只要节点不为null，那么count就+1，最后返回的count值就是链表长度了。（和单链表方法一致）
public int size(){
ListNode cur=this.head;
int count=0 ;//引入局部变量count来计数
while(cur!=null){
count++;//当cur不为空时，计数器+1
cur=cur.next;//cur往后走，指向下一个节点
}
return count;//返回双链表长度
}
查找是否包含关键字key是否在双链表中
传入关键字key，引入局部变量cur遍历链表，如果在遍历过程中遇到和key相同的元素则返回true，否则返回false。（和单链表方法一致）
public boolean contains(int key){
ListNode cur=this.head;//引入局部变量cur代替头结点遍历链表
while(cur!=null){
if(cur.value==key)//相等时说明链表中包含了关键字key返回true
return true;
cur=cur.next;//遍历下一个节点
}
//当变量cur为空时，说明遍历结束并跳出循环，链表中没有包含这个关键字，返回false
return false;
}
头插法
所谓头插法就是将一个节点插入到头结点的前面。首先我们要先判断一下头结点是否为空，如果为空的话，那么所创建的新节点就直接为头结点和尾结点；如若不为空，则新插入的节点的后继指向原来的头结点，原来头结点的前驱指向新插入的节点，最后再把新插入的节点设置为头结点。
public void addFirst(int data){
ListNode node=new ListNode(data);//创建一个新节点，存入要插入的数据
if(this.head==null){//判断头结点是否为空，若头结点为空，则说明是第一次插入
this.head=node;//直接将头结点和尾结点指向插入节点即可
this.last=node;
}
else{//若不是第一次插入
node.next=this.head;//新插入的节点的后继指向头结点
this.head.prev=node;//将原来的头结点的前驱指向新插入的节点
this.head=node;//最后将新插入的节点设置为头结点
}
}
尾插法
尾插法和头插法类似，必须先判断头结点是否为空，若为空则说明是第一次插入，直接把头结点和尾结点指向新插入的节点即可，若不为空，找到双链表的last节点，然后将新节点插入即可。
public void addLast(int data){
ListNode node=new ListNode(data);//创建一个新节点，存入要插入的数据
if(this.head==null){//判断头结点是否为空，若头结点为空，则说明是第一次插入
this.head=node;//直接将头结点和尾结点指向插入节点即可
this.last=node;
}
else{//若不是第一次插入
this.last.next=node;//将原来尾结点的后继指向新插入的节点
node.prev=this.last;//新节点的前驱为原先的尾结点
this.last=node;//最后把新插入的节点变成尾结点
}
}
任意位置插入,第一个数据节点为0号下标
首先我们需要先判断一下插入位置是否合理，然后我们如果要在任意位置插入一个节点，则必须要先找到插入位置，然后将新创建的节点插到当前节点和前一个节点之间即可，由于是双链表，所以要注意前驱和后继的改变。
//寻找插入位置
public ListNode searchIndex(int index){
ListNode cur=this.head;//引入局部变量count来计数
while(index!=0){//遍历链表，找到要插入的那个位置
cur=cur.next;//cur往后走，指向下一个节点
index--;//下标-1
}
return cur;
}
//任意位置插入，第一个数据节点为0号下标
public void addIndex(int index,int data){
ListNode node=new ListNode(data);//创建一个新节点，存入要插入的数据
//判断插入位置是否合法
if(index<0||index>size()){
System.out.println("插入位置不合法");
return;
}
//若插入位置为0，则为头插，直接调用头插法即可
if(index==0){
addFirst(data);
return ;
}
//若插入位置为链表长度大小的位置，则为尾插，直接调用尾插法即可
if(index==size()){
addLast(data);
return;
}
ListNode cur=searchIndex(index);//引用变量cur来接收searchIndex方法所返回的插入位置
node.next=cur.prev.next;//使新插入节点的后继指向插入位置前驱的后继节点
cur.prev.next=node;//插入位置的前驱节点的后继节点就是新插入节点
node.prev=cur.prev;//新插入节点的前驱节点变成了插入位置的那个前驱节点
cur.prev=node;//所插入位置的前驱节点就变成了新插入的节点
}
删除第一次出现关键字为key的节点
首先我们要先判断一下链表是否为空（也就是头节点是否为空），其次我们还要看要删除的key节点是否为头节点，若为头节点，则直接将头结点的引用指向下一个节点，下个节点就成为了头节点；若关键字在尾巴结点，则将尾巴节点的上一个节点设置为新尾节点；若关键字是中间节点，则将key节点的前一个节点的后继指向key节点的后一个节点，key节点的后一节点的前驱指向key节点前一个节点。
public void remove(int key){
ListNode cur=this.head;//引用变量cur代替头结点
while(cur!=null){//对链表进行遍历
if(cur.value==key){//如果节点的值与关键字key相等进入循环
if(cur==this.head){//如果头结点为关键字key
this.head=this.head.next;//头结点直接指向下一个节点
if(this.head!=null) {//如果链表中只有一个元素要检查一下
this.head.prev = null;//否则会空指针异常
}
else{
this.last=null;
}
}
else{//如果关键字在尾部或在中间位置
cur.prev.next=cur.next;//让当前节点的前一个节点的后继指向当前节点的下个节点
if(cur==this.last){//关键字key在尾部
last=last.prev;//尾部节点的前一个节点为最后一个节点
}else{
//为中间节点
cur.next.prev=cur.prev;//当前节点后一个节点的前驱指向当前节点的前一个节点
}
}
return ;//找到关键字key后中断
}
cur=cur.next;//若没找到则cur继续指向下一个节点
}
}
删除所有值为key的节点
和上边删除第一次出现关键字为key的节点方法类似，只不过上面那个在找到一个关键字为key的节点后就不往下执行了，这个删除所有值为key的节点是，在找到第一key后继续往下执行，直到找到所有的再停下来。
public void remove(int key){
ListNode cur=this.head;//引用变量cur代替头结点
while(cur!=null){//对链表进行遍历
if(cur.value==key){//如果节点的值与关键字key相等进入循环
if(cur==this.head){//如果头结点为关键字key
this.head=this.head.next;//头结点直接指向下一个节点
if(this.head!=null) {//如果链表中只有一个元素要检查一下
this.head.prev = null;//否则会空指针异常
}
else{
this.last=null;
}
}
else{//如果关键字在尾部或在中间位置
cur.prev.next=cur.next;//让当前节点的前一个节点的后继指向当前节点的下个节点
if(cur==this.last){//关键字key在尾部
last=last.prev;//尾部节点的前一个节点为最后一个节点
}else{
//为中间节点
cur.next.prev=cur.prev;//当前节点后一个节点的前驱指向当前节点的前一个节点
}
}
}
cur=cur.next;//若没找到则cur继续指向下一个节点
}
}
置空链表
与置空单链表方法类似，只不过这多了个置空节点的前驱，而且尾巴节点也要置为空。
public void clear(){
//在头结点不为空的情况下
while(this.head!=null){
ListNode curNext=this.head.next;//引用变量curNext来保存头结点的下一个节点
this.head.next=null;//把头结点中的next置为null
this.head.prev=null;//把头结点中的prev置为null
this.head=curNext;//把下一个节点置为头结点
}
this.last=null;//尾巴节点也要置为空
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）