Thread - Data Structure

#dsa #java #old-post
Last updated: Nov. 3rd 2024
Running thread for Data Structure
Written by: Yuk
1
2
3
4
5
6
Thread info: Last updated: 03-11-2024
    - 30-10-2024: Added MyArrayList and MyLinkedList
    - 31-10-2024: Moved Test Classes to a separate section
                  Finished MyLinkedList
                  Added MyDoublyLinkedList
    - 03-11-2024: Finished MyDoublyLinkedList
Markdown

Data Structure

We implement basic data structures that will only work with int first, evaluate the performance of the operations, and provide test classes using JUnit for each of the data structure.

Linear Data Structure

Interface and Abstract Parent Class for Lists

To truly follow the fashion of Java, we use interface MyList and MyAbstractList. These classes will ensure consistency and handle basic operations like isEmpty(), toString(),…

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
import java.util.Iterator;
import java.util.List;

public interface MyList {

    int size();

    void append(int x);

    void insertAtIndex(int x, int i);

    void setAtIndex(int x, int i);

    int get(int i);

    void deleteAtIndex(int i);

    void deleteAllOf(int x);

    int[] toArray();

    List<Integer> toList();

    boolean isEmpty();

    Iterator<Integer> iterator();

}
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public abstract class MyAbstractList implements MyList {

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

    public void checkBound(int index, int limit) {
        if (index < 0 || index >= limit)
            throw new IndexOutOfBoundsException
            ("Invalid index: " + index + " for length: " + size());
    }

    @Override
    public String toString() {
        StringBuilder list = new StringBuilder("[");
        for (int i = 0; i < size(); i++) {
            if (i == size() - 1) list.append(get(i));
            else list.append(get(i)).append(", ");
        }
        return list.append("]").toString();
    }

}
Java

MyArrayList

A resizable array that can grow or shrink as needed. It offers efficient random access, insertion, and removal of elements. It’s widely used in data structures and algorithms due to its flexibility and ease of use. Below is the full implementation and test class, we will evaluate each operation methods. (You can use the 🔼 button to collapse the codeblocks, the 🔼 button at the header on top of the page will allow you to collapse all codeblocks)

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
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class MyArrayList extends MyAbstractList {

    private static final int DEFAULT_CAPACITY = 4;
    private int size;
    private int[] data;

    public MyArrayList() {
        data = new int[DEFAULT_CAPACITY];
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void append(int x) {
        if (size >= data.length) enlarge();
        data[size++] = x;
    }

    @Override
    public void insertAtIndex(int x, int i) {
        checkBound(i, size + 1);
        if (i == size) append(x);
        else {
            if (size >= data.length) enlarge();
            else {
                System.arraycopy(data, i, data, i + 1, size - i);
                data[i] = x;
                size++;
            }
        }
    }

    @Override
    public void setAtIndex(int x, int i) {
        checkBound(i, size);
        data[i] = x;
    }

    @Override
    public int get(int i) {
        checkBound(i, size);
        return data[i];
    }

    @Override
    public void deleteAtIndex(int i) {
        checkBound(i, size);
        System.arraycopy(data, i + 1, data, i, size - i - 1);
        size--;
        correct();
    }

    @Override
    public void deleteAllOf(int x) {
        int shiftCount = 0;

        for (int i = 0; i < size; i++) {
            if (data[i] == x) {
                shiftCount++;
            } else if (shiftCount > 0) {
                data[i - shiftCount] = data[i];
            }
        }

        size -= shiftCount;
        correct();
    }

    @Override
    public int[] toArray() {
        return Arrays.copyOf(data, size);
    }

    @Override
    public List<Integer> toList() {
        return Arrays.stream(toArray()).boxed().toList();
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {

            int pos = 0;

            @Override
            public boolean hasNext() {
                return pos < size;
            }

            @Override
            public Integer next() {
                if (hasNext()) {
                    return data[pos++];
                } else throw new NoSuchElementException();
            }
        };
    }

    private void enlarge() {
        int[] enlargedData = new int[data.length * 2];
        System.arraycopy(data, 0, enlargedData, 0, size);
        data = enlargedData;
    }

    private void correct() {
        for (int i = size; i < data.length; i++) {
            data[i] = 0;
        }
    }

}
Java

Helper Methods

1
2
3
4
5
private void enlarge() {
    int[] enlargedData = new int[data.length * 2];
    System.arraycopy(data, 0, enlargedData, 0, size);
    data = enlargedData;
}
Java
  • Time complexity: O(n)∣Ω(n)∣Θ(n)O(n) \mid \Omega(n) \mid \Theta(n)
1
2
3
4
5
private void correct() {
    for (int i = size; i < data.length; i++) {
        data[i] = 0;
    }
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(k)O(n) \mid \Omega(1) \mid \Theta(k)
  • Where kk = data.length - size

Insertion

1
2
3
4
public void append(int x) {
    if (size >= data.length) enlarge();
    data[size++] = x;
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(1)O(n) \mid \Omega(1) \mid \Theta(1)
  • O(n)O(n) because the method may call enlarge()
1
2
3
4
5
6
7
8
9
10
11
12
public void insertAtIndex(int x, int i) {
    checkBound(i, size + 1);
    if (i == size) append(x);
    else {
        if (size >= data.length) enlarge();
        else {
            System.arraycopy(data, i, data, i + 1, size - i);
            data[i] = x;
            size++;
        }
    }
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)

Modification and Access

1
2
3
4
5
6
7
8
9
public void setAtIndex(int x, int i) {
    checkBound(i, size);
    data[i] = x;
}

public int get(int i) {
    checkBound(i, size);
    return data[i];
}
Java
  • Time complexity: O(1)O(1)

Deletion

1
2
3
4
5
6
public void deleteAtIndex(int i) {
    checkBound(i, size);
    System.arraycopy(data, i + 1, data, i, size - i - 1);
    size--;
    correct();
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void deleteAllOf(int x) {
    int shiftCount = 0;

    for (int i = 0; i < size; i++) {
        if (data[i] == x) {
            shiftCount++;
        } else if (shiftCount > 0) {
            data[i - shiftCount] = data[i];
        }
    }

    size -= shiftCount;
    correct();
}
Java
  • Time complexity: O(n)∣Ω(n)∣Θ(n)O(n) \mid \Omega(n) \mid \Theta(n)

MyLinkedList

A linear data structure where elements are not stored in contiguous memory locations. Instead, each element, called a node, contains data and a reference (link) to the next node in the sequence. This allows for dynamic memory allocation and efficient insertion and deletion of elements, especially at the beginning or middle of the list. Class MyLinkedList implements a singly linked list, utilizing class Node with a single pointer and one-way traversal.

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
164
165
166
167
168
169
170
171
172
173
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;

public class MyLinkedList extends MyAbstractList {

    private Node head;
    private int size;

    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public MyLinkedList() {
        head = null;
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void append(int x) {
        if (head == null) {
            head = new Node(x);
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new Node(x);
        }
        size++;
    }

    @Override
    public void insertAtIndex(int x, int i) {
        checkBound(i, size + 1);
        if (i == 0) {
            Node newNode = new Node(x);
            newNode.next = head;
            head = newNode;
        } else {
            Node current = head;
            for (int j = 0; j < i - 1; j++) {
                current = current.next;
            }
            Node newNode = new Node(x);
            newNode.next = current.next;
            current.next = newNode;
        }
        size++;
    }

    public void insertAtHead(int x) {
        insertAtIndex(x, 0);
    }

    public void insertAtTail(int x) {
        insertAtIndex(x, size);
    }

    @Override
    public void setAtIndex(int x, int i) {
        checkBound(i, size);
        Node current = head;
        for (int j = 0; j < i; j++) {
            current = current.next;
        }
        current.val = x;
    }

    @Override
    public int get(int i) {
        checkBound(i, size);
        Node current = head;
        for (int j = 0; j < i; j++) {
            current = current.next;
        }
        return current.val;
    }

    @Override
    public void deleteAtIndex(int i) {
        checkBound(i, size);
        if (i == 0) {
            head = head.next;
        } else {
            Node current = head;
            for (int j = 0; j < i - 1; j++) {
                current = current.next;
            }
            current.next = current.next.next;
        }
        size--;
    }

    public void deleteAtHead() {
        deleteAtIndex(0);
    }

    public void deleteAtTail() {
        deleteAtIndex(size - 1);
    }

    @Override
    public void deleteAllOf(int x) {
        Node dummy = new Node(0);
        dummy.next = head;
        Node current = dummy;
        while (current.next != null) {
            if (current.next.val == x) {
                current.next = current.next.next;
                size--;
            } else {
                current = current.next;
            }
        }
        head = dummy.next;
    }

    @Override
    public int[] toArray() {
        int[] array = new int[size];
        Node current = head;
        for (int i = 0; i < size; i++) {
            array[i] = current.val;
            current = current.next;
        }
        return array;
    }

    @Override
    public List<Integer> toList() {
        List<Integer> list = new LinkedList<>();
        Node current = head;
        while (current != null) {
            list.add(current.val);
            current = current.next;
        }
        return list;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {

            Node current = head;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public Integer next() {
                if (hasNext()) {
                    int val = current.val;
                    current = current.next;
                    return val;
                } else throw new NoSuchElementException();
            }
        };
    }
}
Java

Insertion

1
2
3
4
5
6
7
8
9
10
11
12
public void append(int x) {
    if (head == null) {
        head = new Node(x);
    } else {
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(x);
    }
    size++;
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void insertAtIndex(int x, int i) {
    checkBound(i, size + 1);
    if (i == 0) {
        Node newNode = new Node(x);
        newNode.next = head;
        head = newNode;
    } else {
        Node current = head;
        for (int j = 0; j < i - 1; j++) {
            current = current.next;
        }
        Node newNode = new Node(x);
        newNode.next = current.next;
        current.next = newNode;
    }
    size++;
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)
1
2
3
4
5
6
7
public void insertAtHead(int x) {
    insertAtIndex(x, 0);
}

public void insertAtTail(int x) {
    insertAtIndex(x, size);
}
Java
  • insertAtHead(int x) Time complexity: O(1)∣Ω(1)∣Θ(1)O(1) \mid \Omega(1) \mid \Theta(1)
  • insertAtTail(int x) Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)

Modification and Access

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void setAtIndex(int x, int i) {
    checkBound(i, size);
    Node current = head;
    for (int j = 0; j < i; j++) {
        current = current.next;
    }
    current.val = x;
}

public int get(int i) {
    checkBound(i, size);
    Node current = head;
    for (int j = 0; j < i; j++) {
        current = current.next;
    }
    return current.val;
}
Java
  • setAtIndex(int x, int i) Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)
  • get(int i) Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)

Deletion

1
2
3
4
5
6
7
8
9
10
11
12
13
public void deleteAtIndex(int i) {
    checkBound(i, size);
    if (i == 0) {
        head = head.next;
    } else {
        Node current = head;
        for (int j = 0; j < i - 1; j++) {
            current = current.next;
        }
        current.next = current.next.next;
    }
    size--;
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)
1
2
3
4
5
6
7
public void deleteAtHead() {
    deleteAtIndex(0);
}

public void deleteAtTail() {
    deleteAtIndex(size - 1);
}
Java
  • deleteAtHead() Time complexity: O(1)∣Ω(1)∣Θ(1)O(1) \mid \Omega(1) \mid \Theta(1)
  • deleteAtTail() Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void deleteAllOf(int x) {
    Node dummy = new Node(0);
    dummy.next = head;
    Node current = dummy;
    while (current.next != null) {
        if (current.next.val == x) {
            current.next = current.next.next;
            size--;
        } else {
            current = current.next;
        }
    }
    head = dummy.next;
}
Java
  • Time complexity: O(n)∣Ω(n)∣Θ(n)O(n) \mid \Omega(n) \mid \Theta(n)

MyDoublyLinkedList

Class MyDoublyLinkedList implements a doubly linked list, where each node contains data and references to both the next and previous nodes. This bidirectional linking enables efficient insertion, deletion, and traversal in both forward and backward directions, making it a versatile data structure for various applications.

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class MyDoublyLinkedList extends MyAbstractList {

    private Node head;
    private Node tail;
    private int size;

    static class Node {
        int val;
        Node next;
        Node prev;

        public Node(int val) {
            this.val = val;
        }
    }

    public MyDoublyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void append(int x) {
        Node newNode = new Node(x);
        if (head == null) {
            head = newNode;
            tail = head;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    @Override
    public void insertAtIndex(int x, int i) {
        checkBound(i, size + 1);

        if (i == 0) {
            insertAtHead(x);
            return;
        }

        if (i == size) {
            append(x);
            return;
        }

        Node newNode = new Node(x);
        Node current = dynamicTraversal(i);

        newNode.prev = current.prev;
        newNode.next = current;
        current.prev.next = newNode;
        current.prev = newNode;

        size++;
    }

    public void insertAtHead(int x) {
        Node newNode = new Node(x);
        if (head == null) {
            head = newNode;
            tail = head;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    public void insertAtTail(int x) {
        append(x);
    }

    @Override
    public void setAtIndex(int x, int i) {
        checkBound(i, size);
        dynamicTraversal(i).val = x;
    }

    @Override
    public int get(int i) {
        checkBound(i, size);
        return dynamicTraversal(i).val;
    }

    @Override
    public void deleteAtIndex(int i) {
        checkBound(i, size);

        if (size == 1) {
            head = null;
            tail = null;
        } else if (i == 0) {
            deleteAtHead();
            return;
        } else if (i == size - 1) {
            deleteAtTail();
            return;
        } else {
            Node current = dynamicTraversal(i);
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }

        size--;
    }

    public void deleteAtHead() {
        if (size == 0) return;

        if (size == 1) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }

        size--;
    }

    public void deleteAtTail() {
        if (size == 0) return;

        if (size == 1) {
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }

        size--;
    }

    @Override
    public void deleteAllOf(int x) {
        Node current = head;
        while (current != null) {
            if (current.val == x) {
                if (current == head) {
                    deleteAtHead();
                    current = head;
                } else if (current == tail) {
                    deleteAtTail();
                    break;
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                    current = current.next;
                    size--;
                }
            } else {
                current = current.next;
            }
        }
    }

    @Override
    public int[] toArray() {
        int[] arr = new int[size];
        Node current = head;
        for (int i = 0; current != null; i++) {
            arr[i] = current.val;
            current = current.next;
        }
        return arr;
    }

    @Override
    public List<Integer> toList() {
        List<Integer> list = new ArrayList<>();
        Node current = head;
        while (current != null) {
            list.add(current.val);
            current = current.next;
        }
        return list;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            private Node current = head;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                int val = current.val;
                current = current.next;
                return val;
            }
        };
    }

    private Node dynamicTraversal(int i) {
        Node current;
        if (i < size / 2) {
            current = head;
            for (int j = 0; j < i; j++) {
                current = current.next;
            }
        } else {
            current = tail;
            for (int j = size - 1; j > i; j--) {
                current = current.prev;
            }
        }
        return current;
    }

}
Java

Helper Method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private Node dynamicTraversal(int i) {
    Node current;
    if (i < size / 2) {
        current = head;
        for (int j = 0; j < i; j++) {
            current = current.next;
        }
    } else {
        current = tail;
        for (int j = size - 1; j > i; j--) {
            current = current.prev;
        }
    }
    return current;
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)

Insertion

1
2
3
4
5
6
7
8
9
10
11
12
public void append(int x) {
    Node newNode = new Node(x);
    if (head == null) {
        head = newNode;
        tail = head;
    } else {
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }
    size++;
}
Java
  • Time complexity: O(1)∣Ω(1)∣Θ(1)O(1) \mid \Omega(1) \mid \Theta(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void insertAtIndex(int x, int i) {
    checkBound(i, size + 1);

    if (i == 0) {
        insertAtHead(x);
        return;
    }

    if (i == size) {
        append(x);
        return;
    }

    Node newNode = new Node(x);
    Node current = dynamicTraversal(i);

    newNode.prev = current.prev;
    newNode.next = current;
    current.prev.next = newNode;
    current.prev = newNode;

    size++;
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)
1
2
3
4
5
6
7
8
9
10
11
12
public void insertAtHead(int x) {
    Node newNode = new Node(x);
    if (head == null) {
        head = newNode;
        tail = head;
    } else {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
    size++;
}
Java
  • Time complexity: O(1)∣Ω(1)∣Θ(1)O(1) \mid \Omega(1) \mid \Theta(1)
1
2
3
public void insertAtTail(int x) {
    append(x);
}
Java
  • Time complexity: O(1)∣Ω(1)∣Θ(1)O(1) \mid \Omega(1) \mid \Theta(1)

Modification and Access

1
2
3
4
5
6
7
8
9
public void setAtIndex(int x, int i) {
    checkBound(i, size);
    dynamicTraversal(i).val = x;
}

public int get(int i) {
    checkBound(i, size);
    return dynamicTraversal(i).val;
}
Java
  • setAtIndex(int x, int i) Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)
  • get(int i) Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)

Deletion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void deleteAtIndex(int i) {
    checkBound(i, size);

    if (size == 1) {
        head = null;
        tail = null;
    } else if (i == 0) {
        deleteAtHead();
        return;
    } else if (i == size - 1) {
        deleteAtTail();
        return;
    } else {
        Node current = dynamicTraversal(i);
        current.prev.next = current.next;
        current.next.prev = current.prev;
    }

    size--;
}
Java
  • Time complexity: O(n)∣Ω(1)∣Θ(n)O(n) \mid \Omega(1) \mid \Theta(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
public void deleteAtHead() {
    if (size == 0) return;

    if (size == 1) {
            head = null;
            tail = null;
    } else {
        head = head.next;
        head.prev = null;
    }

    size--;
}
Java
  • Time complexity: O(1)∣Ω(1)∣Θ(1)O(1) \mid \Omega(1) \mid \Theta(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
public void deleteAtTail() {
    if (size == 0) return;

    if (size == 1) {
        head = null;
        tail = null;
    } else {
        tail = tail.prev;
        tail.next = null;
    }

    size--;
}
Java
  • Time complexity: O(1)∣Ω(1)∣Θ(1)O(1) \mid \Omega(1) \mid \Theta(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void deleteAllOf(int x) {
    Node current = head;
    while (current != null) {
        if (current.val == x) {
            if (current == head) {
                deleteAtHead();
                current = head;
            } else if (current == tail) {
                deleteAtTail();
                break;
            } else {
                current.prev.next = current.next;
                current.next.prev = current.prev;
                current = current.next;
                size--;
            }
        } else {
            current = current.next;
        }
    }
}
Java
  • Time complexity: O(n)∣Ω(n)∣Θ(n)O(n) \mid \Omega(n) \mid \Theta(n)

MyStack

Hash-Based Data Structure

Tree Data Structure

Test Classes

MyArrayList

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
package test;

import data_structure.non_generic.MyArrayList;
import data_structure.non_generic.MyList;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Iterator;
import java.util.List;

import static org.junit.jupiter.api.Assertions.*;

public class TestMyArrayList {

    private MyList myList;

    @BeforeEach
    void setup() {
        myList = new MyArrayList();
    }

    @Test
    void testSize() {
        assertEquals(0, myList.size());
        myList.append(1);
        assertEquals(1, myList.size());
        myList.append(2);
        assertEquals(2, myList.size());
    }

    @Test
    void testAppend() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testInsertAtIndex() {
        myList.append(1);
        myList.append(3);
        myList.insertAtIndex(2, 1);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testSetAtIndex() {
        myList.append(1);
        myList.append(2);
        myList.setAtIndex(3, 1);
        assertEquals(1, myList.get(0));
        assertEquals(3, myList.get(1));
    }

    @Test
    void testGet() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testDeleteAtIndex() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.deleteAtIndex(1);
        assertEquals(1, myList.get(0));
        assertEquals(3, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testDeleteAllOf() {
        myList.append(1);
        myList.append(2);
        myList.append(1);
        myList.append(3);
        myList.deleteAllOf(1);
        assertEquals(2, myList.get(0));
        assertEquals(3, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testToArray() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        int[] arr = myList.toArray();
        assertArrayEquals(new int[]{1, 2, 3}, arr);
    }

    @Test
    void testToList() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        List<Integer> list = myList.toList();
        assertEquals(List.of(1, 2, 3), list);
    }

    @Test
    void testIterator() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        Iterator<Integer> iterator = myList.iterator();
        assertTrue(iterator.hasNext());
        assertEquals(1, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(2, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(3, iterator.next());
        assertFalse(iterator.hasNext());
    }

    @Test
    void testEdgeCases() {
        // Test inserting at the beginning
        myList.insertAtIndex(1, 0);
        assertEquals(1, myList.get(0));
        assertEquals(1, myList.size());

        // Test appending at the end
        myList.append(2);
        assertEquals(2, myList.get(1));
        assertEquals(2, myList.size());

        // Test setting at the beginning
        myList.setAtIndex(3, 0);
        assertEquals(3, myList.get(0));

        // Test setting at the end
        myList.setAtIndex(4, 1);
        assertEquals(4, myList.get(1));

        // Test deleting at the beginning
        myList.deleteAtIndex(0);
        assertEquals(4, myList.get(0));
        assertEquals(1, myList.size());

        // Test deleting at the end
        myList.deleteAtIndex(0);
        assertEquals(0, myList.size());

        // Test inserting out of bounds (should throw exception)
        assertThrows(IndexOutOfBoundsException.class, () -> myList.insertAtIndex(5, 5));

        // Test getting out of bounds
        assertThrows(IndexOutOfBoundsException.class, () -> myList.get(2));

        // Test setting out of bounds
        assertThrows(IndexOutOfBoundsException.class, () -> myList.setAtIndex(10, 1));
    }

    @Test
    void testEmptyListOperations() {
        // Ensure delete operation on empty list doesn't throw unexpected errors
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(0));

        // Ensure get operation on empty list throws an exception
        assertThrows(IndexOutOfBoundsException.class, () -> myList.get(0));

        // Ensure set operation on empty list throws an exception
        assertThrows(IndexOutOfBoundsException.class, () -> myList.setAtIndex(1, 0));
    }

    @Test
    void testToString() {
        assertEquals("[]", myList.toString());
        myList.append(1);
        assertEquals("[1]", myList.toString());
        myList.append(2);
        assertEquals("[1, 2]", myList.toString());
        myList.append(3);
        assertEquals("[1, 2, 3]", myList.toString());
    }

    @Test
    void testLargeNumberOfElements() {
        // Append a large number of elements to test list expansion
        for (int i = 0; i < 1000; i++) {
            myList.append(i);
        }
        assertEquals(1000, myList.size());
        assertEquals(999, myList.get(999));

        // Delete some elements and check if the list is updated correctly
        myList.deleteAtIndex(500);
        assertEquals(999, myList.size());
        assertEquals(501, myList.get(500));
    }

    @Test
    void testEdgeCasesEnhanced() {
        // Test appending minimum and maximum integer values
        myList.append(Integer.MIN_VALUE);
        myList.append(Integer.MAX_VALUE);
        assertEquals(Integer.MIN_VALUE, myList.get(0));
        assertEquals(Integer.MAX_VALUE, myList.get(1));

        // Test inserting in the middle of a list with minimum and maximum values
        myList.insertAtIndex(0, 1);
        assertEquals(Integer.MIN_VALUE, myList.get(0));
        assertEquals(0, myList.get(1));
        assertEquals(Integer.MAX_VALUE, myList.get(2));

        // Test deleting non-existent element
        myList.deleteAllOf(999); // Element 999 is not in the list
        assertEquals(3, myList.size());

        // Test appending and deleting duplicate values
        myList.append(5);
        myList.append(5);
        myList.deleteAllOf(5);
        assertEquals(3, myList.size()); // Only the original three elements should remain

        // Test consecutive deletions
        myList.deleteAtIndex(0);
        myList.deleteAtIndex(0);
        myList.deleteAtIndex(0);
        assertTrue(myList.isEmpty());

        // Test appending and getting a very large number of duplicates
        for (int i = 0; i < 100; i++) {
            myList.append(42);
        }
        assertEquals(100, myList.size());
        assertEquals(42, myList.get(99));
        myList.deleteAllOf(42);
        assertTrue(myList.isEmpty());
    }

}
Java

MyLinkedList

Note: All linked list implementation in this thread uses this test class.

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
package test;

import data_structure.non_generic.MyLinkedList;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import static org.junit.jupiter.api.Assertions.*;

public class TestMyLinkedList {

    private MyLinkedList myList;

    @BeforeEach
    void setup() {
        myList = new MyLinkedList();
    }

    @Test
    void testSize() {
        assertEquals(0, myList.size());
        myList.append(1);
        assertEquals(1, myList.size());
        myList.append(2);
        assertEquals(2, myList.size());
    }

    @Test
    void testAppend() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testInsertAtIndex() {
        myList.append(1);
        myList.append(3);
        myList.insertAtIndex(2, 1);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testInsertAtHead() {
        myList.insertAtHead(1);
        myList.insertAtHead(2);
        assertEquals(2, myList.get(0));
        assertEquals(1, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testInsertAtTail() {
        myList.insertAtTail(1);
        myList.insertAtTail(2);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testSetAtIndex() {
        myList.append(1);
        myList.append(2);
        myList.setAtIndex(3, 1);
        assertEquals(1, myList.get(0));
        assertEquals(3, myList.get(1));
    }

    @Test
    void testGet() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        assertEquals(1, myList.get(0));
        assertEquals(2, myList.get(1));
        assertEquals(3, myList.get(2));
    }

    @Test
    void testDeleteAtIndex() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.deleteAtIndex(1);
        assertEquals(1, myList.get(0));
        assertEquals(3, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testDeleteAtHead() {
        myList.append(1);
        myList.append(2);
        myList.deleteAtHead();
        assertEquals(2, myList.get(0));
        assertEquals(1, myList.size());
    }

    @Test
    void testDeleteAtTail() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.deleteAtTail();
        assertEquals(2, myList.get(1));
        assertEquals(2, myList.size());
    }

    @Test
    void testDeleteAllOf() {
        myList.append(1);
        myList.append(2);
        myList.append(1);
        myList.append(3);
        myList.deleteAllOf(1);
        assertEquals(2, myList.get(0));
        assertEquals(3, myList.get(1));
        assertEquals(2, myList.size());
        myList.deleteAllOf(1);
        myList.deleteAllOf(0);
        assertEquals(2, myList.size());
    }

    @Test
    void testToArray() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        int[] arr = myList.toArray();
        assertArrayEquals(new int[]{1, 2, 3}, arr);
    }

    @Test
    void testToList() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        List<Integer> list = myList.toList();
        assertEquals(List.of(1, 2, 3), list);
    }

    @Test
    void testIterator() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        Iterator<Integer> iterator = myList.iterator();
        assertTrue(iterator.hasNext());
        assertEquals(1, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(2, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(3, iterator.next());
        assertFalse(iterator.hasNext());
    }

    @Test
    void testIteratorEdgeCases() {
        Iterator<Integer> iterator = myList.iterator();
        assertFalse(iterator.hasNext());
        assertThrows(NoSuchElementException.class, iterator::next);

        myList.append(1);
        myList.append(2);
        iterator = myList.iterator();
        assertTrue(iterator.hasNext());
        assertEquals(1, iterator.next());
        assertEquals(2, iterator.next());
        assertFalse(iterator.hasNext());
    }

    @Test
    void testToString() {
        assertEquals("[]", myList.toString());
        myList.append(1);
        assertEquals("[1]", myList.toString());
        myList.append(2);
        assertEquals("[1, 2]", myList.toString());
        myList.append(3);
        assertEquals("[1, 2, 3]", myList.toString());
    }

    @Test
    void testBoundaryConditions() {
        // Test inserting and deleting on empty list
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(0));
        assertThrows(IndexOutOfBoundsException.class, () -> myList.get(0));

        // Add to head, delete head, check size adjustments
        myList.insertAtHead(10);
        assertEquals(1, myList.size());
        myList.deleteAtHead();
        assertEquals(0, myList.size());
    }

    @Test
    void testInsertAtInvalidIndex() {
        assertThrows(IndexOutOfBoundsException.class, () -> myList.insertAtIndex(1, -1)); // Negative index
        assertThrows(IndexOutOfBoundsException.class, () -> myList.insertAtIndex(1, 1));  // Index > size
    }

    @Test
    void testDeleteAtInvalidIndex() {
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(-1)); // Negative index
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(0));  // Empty list
        myList.append(1);
        assertThrows(IndexOutOfBoundsException.class, () -> myList.deleteAtIndex(1)); // Index > size
    }

    @Test
    void testSetAtInvalidIndex() {
        assertThrows(IndexOutOfBoundsException.class, () -> myList.setAtIndex(1, -1)); // Negative index
        assertThrows(IndexOutOfBoundsException.class, () -> myList.setAtIndex(1, 0));  // Index > size
    }

    @Test
    void testDeleteAllOfNonExistentValue() {
        myList.append(1);
        myList.append(2);
        myList.deleteAllOf(3); // Value not present
        assertEquals(2, myList.size()); // Size should remain unchanged
    }

    @Test
    void testInsertMultipleElements() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.insertAtIndex(4, 1);
        assertEquals(4, myList.get(1));
        assertEquals(3, myList.get(3));
    }

    @Test
    void testDeleteAllElements() {
        myList.append(1);
        myList.append(2);
        myList.append(3);
        myList.deleteAllOf(1);
        myList.deleteAllOf(2);
        myList.deleteAllOf(3);
        assertEquals(0, myList.size());
        assertTrue(myList.isEmpty());
    }

    @Test
    void testConsecutiveOperations() {
        myList.append(1);
        myList.append(2);
        myList.insertAtIndex(3, 1); // List should be [1, 3, 2]
        assertEquals(3, myList.get(1));
        myList.deleteAtIndex(0); // List should be [3, 2]
        assertEquals(3, myList.get(0));
    }

    @Test
    void testLargeList() {
        for (int i = 0; i < 10000; i++) {
            myList.append(i);
        }
        assertEquals(10000, myList.size());
        assertEquals(9999, myList.get(9999));
    }

    @Test
    void testIteratorAfterModification() {
        myList.append(1);
        myList.append(2);
        Iterator<Integer> iterator = myList.iterator();
        assertTrue(iterator.hasNext());
        assertEquals(1, iterator.next());
        myList.append(3); // Modify list
        assertTrue(iterator.hasNext());
        assertEquals(2, iterator.next());
        assertTrue(iterator.hasNext());
        assertEquals(3, iterator.next());
        assertFalse(iterator.hasNext());
    }

}
Java