关于线性结构中的双向链表如何实现?

前言

在上一篇文章中,主要是给大家介绍了单向链表的特点及其原理,但是我们没有通过代码进行练习。今天我会继续通过一篇文章,来给大家讲解双向链表的内容,尤其是会通过代码来进行链表的操作,希望大家重点关注哦。


全文大约【3500】 字,不说废话,只讲可以让你学到技术、明白原理的纯干货!本文带有丰富的案例及配图视频,让你更好地理解和运用文中的技术概念,并可以给你带来具有足够启迪的思考...

一. 双向链表简介

1. 概念

在上一篇文章中,我们在介绍链表的种类时,曾经提到过双向链表。双向链表相比较于单链表,除数据域外,还具前和后两个指向指针。


双向链表中的结构术语可以解释为:

  • data:链表每个结点中存储的数据域;
  • next:链表每个结点中包含的指向下一个结点地址的指针域;
  • prev:链表每个结点中包含的前一个结点地址的指针域。

2. 编码定义

根据上述对双向链表结点的定义,我们给出双向链表结点结构的Java定义实现:

class DNode{
    Object data;
    Node prev;
    Node next;
}

双向链表是一条真实存在的链表,由多个结点组成。在实际的编程中,通常会标记链表的两个特殊结点,分别为:头结点、尾结点。用另外一个变量size表示链表中元素的个数。

  • 头结点: 链表中的第一个结点
  • 尾结点: 链表中的最后一个元素

因此有如下链表类的定义:

public class DoubleLinkList{
    private int size;//大小
    private DNode head;//头结点
    private DNode last;//尾结点
}

在本篇文章接下来的内容中,我们将利用该DNode、DoubleLinkList两个定义来实现双向链表的各项操作。

二. 常见操作

因为双向链表是单链表的基础上扩展出来的结构,因此双向链表的很多操作与单链表的操作都是相同的,比如:查找元素、更新元素、插入元素、删除元素

1. 查找元素

1.1 查找头结点

因为DoubleLinkList中已经记录了头结点head,因此头结点的查找非常简单,如下:

public Object getHead(){
    if(head == null){
        return null;
    }
    return head.data;
}

时间复杂度为O(1)。

1.2 查找尾结点

与头结点同理,查找尾结点的时间复杂度同样为O(1),编码如下:

public Object getLast(){
    if(last == null){
        return null;
    }
    return last.data;
}

1.3 查找指定位置结点

当需要查找指定位置的结点元素时,双向链表比单链表的实现方式有所不同,原因是: 单链表因为是单向的,因此只能从头结点向后单向查找;但双向链表前后均可查找,因此在进行指定位置查找时,为了提高查找效率,会首先判断要查找的位置处于链表的前半段还是后半段,若前半段则从头结点向后查找,若后半段则从尾结点向前查找,具体编程如下所示:

public Object get(int index){
    //排除边界异常
    if(index <0 || index>=size){
        return null;
    }
	//要查找的位置位于链表前半段
	if(index < (size>>1)){
        DNode x = head;
        for(int i = 0; i < index; i++){
            x = x.next;
        }
        return x.data;
    }else {//要查找的位置位于链表后半段
        DNode x = last;
        for(int i = size - 1; i >= index; i--){
            x = x.prev;
        }
        return x.data;
    }
}

在上述代码中,size >> 1 的写法比较少见,“>>”在计算机编程中代表移位操作。常见的移位操作有两种:

通过实际的编程验证,我们可以知道:执行右移1位操作,变量数据会缩小为原来的1/2。左移相反。同时,我们可以分析出时间复杂度为O(n)。

2. 更新元素

更新元素操作需要两步:

  • 找到要更新的元素
  • 执行更新操作

根据位置的不同,可以将更新操作分为三种情况:更新头结点,更新尾结点,更新指定位置结点。

2.1 更新头结点

更新头结点代码与查找头结点类似,如下:

public boolean updateHead(Object obj){
    if(head == null){
        return false;
    }
	head.data = obj;
	return true;
}

更新头结点的时间复杂度为O(1)。

2.2 更新尾结点

public boolean updateLast(Object obj){
    if(last == null){
        return false;
    }
	last.data = obj;
}

更新尾结点的时间复杂度同样是O(1)。

2.3 更新指定位置结点

public boolean update(int index, Object obj){
    if(index < 0 || index >= size){
        return false;
    }
    if(index < (size>>1)){
        DNode x = head;
        for(int i = 0; i < index; i++){
            x = x.next;
        }
        x.data = obj;
    }else {
        DNode x = last;
        for(int i = size-1; i >= index; i--){
            x = last.prev;
        }
        x.data = obj;
    }
    return true;
}public boolean addHead(Object data){
    DNode h = head;
	DNode newNode = new DNode(null,data,h);
	head = newNode;
	if(h == null);{
        last = newNode;
    }else {
        h.prev = newNode;
    }
	size++;
	return true;
}

如上代码所示,修改指定结点元素的值采用的算法也是:先判断要操作的位置在前半段还是后半段,然后再进行精准查找,最后执行修改操作。

指定位置修改操作的时间复杂度为O(n)。

3. 插入元素

分析过了查找元素和更新元素操作的具体情况,我们很清晰的便能分析出插入元素操作的具体情况,其实也分为三种具体情景:头结点位置插入,尾结点位置插入,指定位置插入元素

3.1 头结点位置插入

public boolean addHead(Object data){
    DNode h = head;
	DNode newNode = new DNode(null,data,h);
	head = newNode;
	if(h == null);{
        last = newNode;
    }else {
        h.prev = newNode;
    }
	size++;
	return true;
}

根据如上代码,我们可以看到,在头结点位置插入新的元素,只需要将新添加的结点置为head结点,同时处理好新结点和原链表中头结点的指向关系即可。很明显,头结点位置插入的时间复杂度为O(1)。

3.2 尾结点位置插入

尾结点插入与头结点插入原理相同,只需要替换为尾结点以及指针的指向。如下所示:

public boolean addLast(Object data){
    DNode l = last;
	DNode newNode = new DNode(l,data,null);
	last = newNode;
	if(last == null){
        head = last;
    }else {
        l.next = newNode;
    }
	size++;
	return true;
}

时间复杂度为O(1)。

3.3 指定位置插入

在进行指定位置插入时,编程代码稍多些,原因是需要以下几步完成:

  • 判断插入的位置是否超范围
  • 若插入的位置在最后,则执行在尾结点的插入逻辑
  • 先根据要插入的位置,查找并获取到对应位置的结点元素
  • 然后执行插入逻辑
public boolean add(int index,Object data){
    if(index < 0 || index > size){
        return false;
    }
    if(index == size){
        addLast(data);
        return true;
    }else {
        //先找到要插入的指定位置的结点
        DNode x = index(index);
    	//执行插入操作
        DNode prevNode = x.prev;
        DNode newNode = new DNode(prevNode,data,x);
        x.prev = newNode;
        if(prevNode == null){
            head = newNode;
        }else {
            prevNode.next = newNode;
        }
        size++;
    }
}

//查找index位置上的结点并返回
public DNode index(int index){
    if( index < 0 || index >= size){
        return null;
    }
	if( index < (size>>1)){
        DNode x = head;
        for(int i = 0; i < index; i++){
            x = x.next;
        }
        return x;
    }else {
        DNode x = last;
        for(int i = size-1; i >= index; i--){
            x = x.prev;
        }
        return x;
    }
}

根据上述代码,我们可以发现插入指定位置的代码,需要用到查找指定位置的操作,先查找再插入,因此时间复杂度同样为O(n)。

4. 删除元素

有了前面的分析经验,我们可以非常自然的分析出删除操作同样分三种:删除头结点、删除尾结点、删除指定结点。接下来,一起来看看详细的情况:

4.1 删除头结点

public Object removeHead(){
    if(head == null){
        return null;
    }
    DNode h = head;
    Object data = h.data;
    DNode next = h.next;
	//将原来头结点的数据域和指针域均赋值为null置空
    h.data = null;
    h.next = null;

    //将当前结点的next作为新的头结点
    head = next;

    //如果next为null,则说明当前链表只有一个节点,删除该节点,则链表的first、last都为null
    if(next == null){
        last = null;
    }else {
        // next要作为新的头节点,则其prev属性为null
        next.prev = null;
    }
    size--;
    return data;
}

删除头结点只涉及头结点的逻辑判断和操作,因此删除头结点时间复杂度为O(1)。

4.2 删除尾结点

与删除头结点原理相同,操作尾结点。代码如下:

public Object removeLast(){
    DNode l = last;
    if(l == null){
        return null;
    }
    Object data = l.data;
    DNode prev = l.prev;
	//将当前尾节点的属性赋值为null,为了GC清理
    l.data = null;
    l.prev = null;
	// 让当前尾节点的prev作为新的尾节点,赋值给last属性
    last = prev;
	// 如果prev为null,则说明当前链表只有一个节点,删除该节点,则链表的first、last都为null
    if(prev == null){
        head = null;
    }else {
        // prev要作为新的尾节点,则其next属性为null
        prev.next = null;
    }
    size--;
    return data;
}

很明显,删除尾结点的时间复杂度为O(1)。

4.3 删除指定结点

删除指定结点的编码实现如下:

public Object remove(int index){
    if(index < 0 || index >= size){
        return null;
    }
	//首先通过查找方法,查找到
	DNode node = index(index;
	//执行删除操作
	Object data = node.data;
	DNode next = node.next;
	DNode prev = node.prev;

	// 如果prev是null,则说明删除的是当前头节点,则将next作为新的头节点,赋值给head
	if(prev == null){
        head = prev;
    }else {
        // 如果删除的不是当前头节点,则将要删除节点的prev与next连接一起,即将prev的next属性赋值成next
        prev.next = next;
        // 如果prev不是null,则赋值为null
        node.prev = null;
    }

	// 如果next是null,则说明删除的是当前尾节点,则将prev作为新的尾节点,赋值给last
	if(next == null){
        last = prev;
    }else {
        // 如果删除的不是当前尾节点,则将要删除节点的prev与next连接一起,即将next的prev赋值成prev
        next.prev = prev;
        // 如果next不是null,则赋值为null
        node.next = null;
    }
	//将要删除的结点的data数据域设置为null
	node.data = null;
	//链表的结点个数-1操作
	size--;
	return data;
}

如上代码所示,删除指定位置的结点元素也需要先执行index(index)查找算法,至于index的实现,在前文介绍指定位置插入结点操作时,已经进行了实现,此处直接进行使用。

我们不难分析得到,删除指定位置的结点的时间复杂度是O(n)。

三. 其他操作

作为一种常见的数据结构,除了对自身结点元素的一些操作,还有一些对链表状态的获取,比如链表的长度,链表是否为空等,这里给大家介绍一下双向链表的一些其他操作。

1. 链表的大小(元素结点的个数)

public int size(){
    return size;
}

2. 判断链表是否为空

public boolean isEmpty(){
    return size == 0;
}

3. 获取链表元素组成的数组

public Object[] toArray(){
    Object[] result = new Object[size];
    int i = 0;
    for(DNode node = head; node != null; node = node.next){
        resunt[i++] = node.data;
    }
    return result;
}

4. 清空链表

public void clear(){
    for(DNode node = head; node != null; ){
        DNode next = node.next;
        node.data = null;
        node.next = null;
        node.prev = null;
        node = next;
    }
    head = last = null;
    size = 0;
}

四. 结语

至此,我们已经连续用两篇文章给大家介绍了链表的相关知识。

在上一篇文章中,我们主要介绍了链表的基础知识和单链表的常规操作, 同时辅以图示来说明各种操作情况。在本篇文章中,主要是从Java编程角度作为切入点,来进一步讲解双向链表的一些操作。 特别是本篇文章中的大量代码实践,需要大家能够理清逻辑关系,希望你可以动手练起来哦。

热门相关:有个人爱你很久   朋友妈妈2017:朋友不在家的日子      我朋友的老姐   小女孩偷窥美味