数据结构之双链表

1.复杂方法的图分析

2.My_LinkedList代码

package My_liNKEDlIST;

public class My_LinkedList implements MY_lIST{
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val){
           this.val = val;
        }

    }
    public ListNode head;
    public ListNode last;
    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
         if(head == null){
             head = node;
             last = node;
         }
         else{
             node.next = head;
             head.prev = node;
             head = node;
         }
    }

    @Override
    public void addLast(int data) {
       ListNode node = new ListNode(data);
       if(head == null){
           head = node;
           last = node;
       }
       else{
           last.next = node;
           node.prev = last;
           last = node;
       }
    }

    @Override
    public void addIndex(int index, int data) throws IndexOutOFException{
          int len = size();
          if(index < 0 || index > len){
              throw new IndexOutOFException("越界了");
          }
          if(index == 0){
              addFirst(data);
              return;
          }
          if(index == len){
              addLast(data);
              return;
          }
          ListNode cur = head;
          ListNode node = new ListNode(data);
          while(index != 0){
              cur = cur.next;
              index--;
          }
           cur.prev.next = node;
           node.next = cur;
           node.prev = cur.prev;
           cur.prev = node;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                return true;
        }
            cur = cur.next;
    }
        return false;
    }

    @Override
    public void remove(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                //如果删除的结点为头结点
                if(cur == head){
                   head = head.next;
                   if(head != null) {
                       head.prev = null;
                   }
                }else {
                     if(cur == last){
                         cur.prev.next = cur.next;
                         last = last.prev;
                     }else {
                         cur.prev.next = cur.next;
                         cur.next.prev = cur.prev;
                     }
                }
                return;
            }
            else{
                cur = cur.next;
            }
        }
    }
    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                //如果删除的结点为头结点
                if(cur == head){
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }
                }else {
                    if(cur.next == null) {
                        cur.prev.next = cur.next;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
                cur = cur.next;
        }
    }
    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while(cur != null){
            System.out.println(cur.val+" ");
            cur = cur.next;
        }
    }

    @Override
    public void clear() {
       ListNode cur = head;
       while(cur != null){
           ListNode tmp = cur.next;
           cur.prev = null;
           cur.next = null;
           cur = tmp;
       }
       this.head = null;
       this.last = null;
    }
}

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

3.接口MY_lIST

public interface MY_lIST {
        // 2、无头双向链表实现

        //头插法
        public void addFirst(int data);
        //尾插法
        public void addLast(int data);
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data);
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key);
        //删除第一次出现关键字为key的节点
        public void remove(int key);
        //删除所有值为key的节点
        public void removeAllKey(int key);
        //得到单链表的长度
        public int size();
        public void display();
        public void clear();
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4.测试类

public class Test {
    public static void main(String[] args) {
             My_LinkedList LIST = new My_LinkedList();
             LIST.addFirst(1);
             LIST.addFirst(1);
             LIST.addFirst(1);
             //LIST.display();
             LIST.addLast(4);
             LIST.addLast(5);
             LIST.addLast(6);
             //LIST.display();
              LIST.addIndex(4,7);
              //LIST.display();
              //LIST.clear();
              //LIST.display();
           //LIST.remove(4);
        LIST.removeAllKey(1);
           LIST.display();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

双链表的思路和单链表大同小异,就是多加了一个前驱指针,希望大家好好学习双链表的代码