数据结构与算法(三)双向链表

Posted on | In

前言

今儿是大年初二,没事继续复习数据结构与算法。复习完双向链表下面就开始栈与队列的复习了。搞完这篇先去北京路溜达溜达。晚上在继续PMP和数据结构预算的学习

什么是双向循环链表

  • 在单链袤的每个结点中,再设置一个指向其前驱结点的指针 域 。所以在双向链表中的结点都有两个指针域, 一个指向直接后继,另一个指向直接 前驱。

双向链表

双向循环链表的生活情境

  • 比出 ,你是一业务员, 家在上海。儒要经常出差,行程就是上海到北京一路上的 城市,找客户谈生意或分公司办理业务。你从上海出发,乘火车路经多个城市停留 后,再乘飞机返回上海,以后,每隔一段时间,你基本还要按照这样的行程开展业务

输入图片说明

  • 你平时都是从上海一路停留到北京的,可是这一次,你得先到北京开会,谁叫北京是首都呢,会就是多。开完会后,你需要例行公事,走访各个城市,此时你怎么办?。有人又出主意了,你可以先飞回上海,一路再乘火车走遍这儿个城市,到了北京后，你在飞回上海。你会感慨,人生中为什么总会有这样出馒主意的人存在呢?真要气死人才行。哪来这么麻烦,我一路从北京坐火车或汽车回去不就完了吗。
  • 对呀,其实生活中类似的小智慧比比皆是,并不会那么的死板教条。我们的单链表,总是从头到尾找结点,难道就不可以正反遍历都可以吗?当然可以,只不过需要加点东西而已。

循环链袭和双向链表的主要差异

  • 双向链表和单向的循环链表操作节本相同，只是在添加和删除操作时多 了一个改变前指针的操作

  • 我们在单链表中,有了 next 指针,这就使得我们要查找下一结点的时同复杂度为0(1)。可是如果我们要查找的是上一结点的话,那最坏的时间复杂度就是 O(n)了,因为我们每次都要从头开始遍历查找。双向链表就可以解决此类问题

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
public class MyLinkedList {
   Node head; // 头指针
    Node current;   // 当前结点对象
    int size;// 结点个数


    // 初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
    public MyLinkedList() {
        this.head = current = new Node(null);
        this.size = 0;// 单向链表，初始长度为零。
        this.head.next = head; //最后一个元素指针域指向头结点
        this.head.prior=head;
    }

    //使用当前结点对象 定位到要操作结点的前一个结点。
    public void index(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数错误！");
        }
        // 说明在头结点之后操作。
        if (index == -1){
            // 第一个数据元素结点的下标是0，那么头结点的下标自然就是-1
            return;
        }
        current = head.next;
        int temp=0;	 	//临时变量 用户循坏判断当前节点是否到达
        while (current!=head && temp<index){
            //循环找到插入节点的前一个节点
            current=current.next;
            temp++;
        }
    }


    /**
     * 删除思路：
     *
     * 1。定位到当前要删除的下标的对像的前一个节点
     * 2. 通过改变当前删除对象前一个节点的指针域。》指向当前要删除对象的指针域指向的下一个节点。
     * 3. 改变删除结点的下一个结点的前指针,指向删除结点的前一个结点
     * @param index
     * @throws Exception
     */
    public void delete(int index) throws Exception {
        // 判断链表是否为空
        if (isEmpty()) {
            throw new Exception("链表为空，无法删除！");
        }
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index - 1);// 定位到要操作结点的前一个结点对象。
        //改变删除结点的前一个节点的next指向为要删除结点的下一个结点
        current.setNext(current.next.next);
        /**
         * 执行 current.setNext(current.next.next)后删除结点的前结点的next就指向了，删除结点的下一个结点了
         * 比如,a,b,c三个结点 删除b的话 此时a->next就指向了c 但是c的前指针还是指向b
         * 所以这个时就改变c的前指针指向a就完成删除操作了
         */
        current.next.setPrior(current);
        size--;
    }

    /**
     * 获取思路：
     * 		从头节点开始遍历。用临时变量temp记录遍历的次数。一直遍历等于index就不会再行循坏，直接取出当前下标的节点
     * @param index
     * @return
     * @throws Exception
     */
    public Object get(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数非法！");
        }
        index(index);
        return current.getElement();
    }

    /**
     * 指定位置插入节点
     * @param index
     * @param obj
     * @throws Exception
     */
    public void insert(int index, Object obj) throws Exception {
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(new Node(obj,current.next));
        current.next.setPrior(current);
        current.next.next.setPrior(current.next);
        size++;

    }

    /**
     * 未指定下标末尾插入
     * @param obj
     * @throws Exception
     */
    public void insert(Object obj) throws Exception {
        /**
         * 1.判断当前节点指向一下节点的指针域是否为空
         * 如果指针域为空 说明是此节点是末尾节点
         * 直接在尾部修改默认节点的指针域执指向新增的节点，并把新增的节点的指针域指向null
         */
        while (current.next!=null){
            //循环判断当前节点指针域是否有下一个节点
            current=current.next;
        }
        //找到末尾节点后。在末尾插入新的结点
        current.setNext(new Node(obj, current.next));
        //当前末尾节点的下一个节点 也就是新增加的结点的前指针指向当前找到的末尾结点
        current.next.setPrior(current);
        //当前末尾结点next-next也就是刚插入的结点的下一个结点前指针指向当前插入的结点
        current.next.next.setPrior(current.next);
        size++;
    }

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

    public int size() {
        return this.size;
    }

    public static void main(String[] args) throws  Exception {
        MyLinkedList list=new MyLinkedList();
        list.insert(0,0);
        list.insert(1,111);
        list.insert(2,222);
        System.out.println("删除之前：");
        for (int i = 0; i < list.size; i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
        list.delete(1);
        System.out.println("删除之后：");
        for (int i = 0; i < list.size; i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

结点模型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Node {
	Object element; //数据域
	Node next;  //后继指针域
	Node prior; //前驱指针域

	//头结点的构造方法
	public Node(Node nextval) {
		this.next = nextval;
	}

	//非头结点的构造方法
	public Node(Object obj, Node nextval) {
		this.element = obj;
		this.next = nextval;
	}

	//获得当前结点的后继结点
	public Node getNext() {
		return this.next;
	}

	//获得当前结点的前驱结点
	public Node getPrior() {
		return this.prior;
	}

	//获得当前的数据域的值
	public Object getElement() {
		return this.element;
	}

	//设置当前结点的后继指针域
	public void setNext(Node nextval) {
		this.next = nextval;
	}

	//设置当前结点的前驱指针域
	public void setPrior(Node priorval) {
		this.prior = priorval;
	}

	//设置当前结点的数据域
	public void setElement(Object obj) {
		this.element = obj;
	}

	public String toString() {
		return this.element.toString();
	}


}

觉得本文不错的话，分享一下给小伙伴吧~