《大话数据结构》----线性表-----链式存储结构(双向链表)实现--java

双向链表

顾名词义,除了指向的next的数据外,还多了一个指向上一个的prior

在单链表中,有了next指针,这就使得我们要查找下一个节点的时间复杂度为O(1).可是如果我们要查找的是上一个节点的话,那最坏的时间复杂度就是O(n)了,因为我们每次都要从头开始遍历查找

为了克服单向性这一圈点,我们的老科学家们,设计出了双向链表,双向链表是在单链表的每个节点中,再设置一个指向前驱节点的指针,所以在双向链表中的节点都有两个指针域,一个指向直接后继,另一个指向直接前驱.

难点

• 头插法和尾插法在初始化的时候,其实就是插入操作,在处理一个节点(插入或删除)的时候,需要顾及处理4个指针.例如针对节点B在前后就有4个相关指针

  a==>b==>c

  a.next=b

  懒得翻译了,看代码应该能看懂

  b.prior=a

  b.next=c

  c.prior=b

• 我解决方式就是在纸上画画,把这几根线画出来,就不会丢也不会乱

代码环节

package com.company;

/**
 * @Author: comfort
 * @Date: 2020/8/2
 */
public class DoubleLinkTest {
    public static void main(String[] args) {
        DoubleLinkList doubleLinkList = new DoubleLinkList();
        String data = "31,21,17,16";
        doubleLinkList.headInit(data.split(","));
        doubleLinkList.out("头插法初始化");

        doubleLinkList.lastInit(data.split(","));
        doubleLinkList.out("尾插法初始化");
        doubleLinkList.delete(2);
        doubleLinkList.out("删除第2个");
        doubleLinkList.delete(1);
        doubleLinkList.out("删除第1个");
    }
}

class DoubleLinkList {

    DoubleLink doubleLink = new DoubleLink();

    public void delete(int index) {
        int k=1;
        DoubleLink delteNode = doubleLink.prior;
        while (delteNode.data != null&&k<index) {
            System.out.print(delteNode.data + " ");
            delteNode = delteNode.prior;
            k++;
        }
        delteNode.prior.next =delteNode.next;
        delteNode.next.prior =delteNode.prior;
    }

    /**
     * 头插法初始化
     */
    public void headInit(String[] data) {
        rootInit();
        DoubleLink node = doubleLink;
        for (String datum : data) {
            DoubleLink n = new DoubleLink();
            n.data = Integer.parseInt(datum);
            //这快繁琐一些,建议自己纸上画画,总共涉及四个指针
            n.next = node.next;
            n.prior = node;

            doubleLink.prior = n;
            node.next = n;
            node = n;
        }

    }

    /**
     *  空链表自己指自己
     */
    private void rootInit() {
        doubleLink.data = null;
        doubleLink.prior = doubleLink;
        doubleLink.next = doubleLink;
    }

    /**
     * 尾插法初始化
     */
    public void lastInit(String[] data) {
        rootInit();
        DoubleLink node = doubleLink;
        for (String datum : data) {
            DoubleLink n = new DoubleLink();
            n.data = Integer.parseInt(datum);
            //这快繁琐一些,建议自己纸上画画,总共涉及四个指针
            n.prior = node.prior;
            node.prior.next = n;
            node.prior = n;
            n.next = node;
            node = n;

        }
    }

    public void out(String str) {
        System.out.println(str);
        System.out.println("右(顺序)链表输出");
        DoubleLink rNode = doubleLink.prior;
        while (rNode.data != null) {
            System.out.print(rNode.data + " ");
            rNode = rNode.prior;
        }
        System.out.println("\n左(倒序)链表输出");
        rNode = doubleLink.next;
        while (rNode.data != null) {
            System.out.print(rNode.data + " ");
            rNode = rNode.next;
        }
        System.out.println("=============");
    }
}

class DoubleLink {
    public Integer data;
    public DoubleLink next;
    public DoubleLink prior;
}

           

输出内容

头插法初始化
右(顺序)链表输出
16 17 21 31 
左(倒序)链表输出
31 21 17 16 
=============
尾插法初始化
右(顺序)链表输出
31 21 17 16 
左(倒序)链表输出
16 17 21 31 
=============
31 删除第2个
右(顺序)链表输出
31 17 16 
左(倒序)链表输出
16 17 31 
=============
删除第1个
右(顺序)链表输出
17 16 
左(倒序)链表输出
16 17 
=============
           

收获和感觉

• 插入懒得写了,本身初始化就是插入操作
• 删除简单验证了一下,因为始终删完就能补上,目前这个代码连续删除第一个,删光是没问题的

• 删除不难, 找到,然后两行

  最后,借用书里的一句话空间换时间