View difference between Paste ID: yAbCQsLL and 60W1UQa5
SHOW: | | - or go back to the newest paste.
1
//
2
// Created by Julio Tentor <jtentor@fi.unju.edu.ar>
3
//
4
5
import java.util.Iterator;
6
7
public class DoubleLinkedList<ELEMENT> implements ILinkedList<ELEMENT> {
8
9
    //region Node Class
10
11
    protected class Node<ELEMENT> {
12
        protected ELEMENT item;
13
        protected Node<ELEMENT> next;
14
        protected Node<ELEMENT> prev;
15
16
        protected Node() {
17
            this(null, null, null);
18
        }
19
        protected Node(ELEMENT item) {
20
            this(item, null, null);
21
        }
22
        protected Node(ELEMENT item, Node<ELEMENT> next) {
23
            this(item, next, null);
24
        }
25
        protected Node(ELEMENT item, Node<ELEMENT> next, Node<ELEMENT> prev) {
26
            this.item = item;
27
            this.next = next;
28
            this.prev = prev;
29
        }
30
31
        @Override
32
        public String toString() {
33
            return this.item.toString();
34
        }
35
    }
36
    //endregion
37
38
    //region Attributes
39
40
    private Node<ELEMENT> head;
41
    private int count;
42
    private Node<ELEMENT> tail;
43
    //endregion
44
45
    //region Constructors
46
47
    public DoubleLinkedList() {
48
        this.head = null;
49
        this.count = 0;
50
        this.tail = null;
51
    }
52
    //endregion
53
54
    //region Linked List Methods
55
56
    // Returns the number of elements in this list.
57
    public int size() {
58
        return this.count;
59
    }
60
61
    public void addFirstRookieVersion(ELEMENT item) {
62
        if (this.size() <= 0) {
63
            this.head = this.tail = new Node<ELEMENT>(item, null, null);
64
            ++this.count;
65
        }
66
        else {
67
            Node<ELEMENT> temp = new Node<ELEMENT>(item, null, null);
68
            temp.next = this.head;
69
            this.head.prev = temp;
70
            this.head = temp;
71
            ++this.count;
72
        }
73
    }
74
    // Inserts the specified element at the beginning of this list.
75
    public void addFirst(ELEMENT item) {
76
        Node<ELEMENT> temp = new Node<ELEMENT>(item, this.head, null);
77
        if (this.size() <= 0) {
78
            this.tail = temp;
79
        }
80
        else {
81
            this.head.prev = temp;
82
        }
83
        this.head = temp;
84
        ++this.count;
85
    }
86
87
    public void addLastRookieVersion(ELEMENT item) {
88
        if (this.size() <= 0) {
89
            this.head = this.tail = new Node<ELEMENT>(item, null, null);
90
            ++this.count;
91
        }
92
        else {
93
            Node<ELEMENT> temp = new Node<ELEMENT>(item, null, null);
94
            temp.prev = this.tail;
95
            this.tail.next = temp;
96
            this.tail = temp;
97
            ++this.count;
98
        }
99
    }
100
    // Appends the specified element to the end of this list.
101
    public void addLast(ELEMENT item) {
102
        Node<ELEMENT> temp = new Node<ELEMENT>(item, null, this.tail);
103
        if (this.size() <= 0) {
104
            this.head = temp;
105
        }
106
        else {
107
            this.tail.next = temp;
108
        }
109
        this.tail = temp;
110
        ++this.count;
111
    }
112
113
    // Removes and returns the first element from this list.
114
    public ELEMENT removeFirst() {
115
        if (this.size() <= 0) {
116
            throw new RuntimeException("La lista está vacía...");
117
        }
118
        ELEMENT item = this.head.item;
119
        this.head = this.head.next;
120
        if (this.head == null) {
121
            this.tail = null;
122
        }
123
        else {
124
            this.head.prev = null;
125
        }
126
        --this.count;
127
        return item;
128
    }
129
130
    // Removes and returns the last element from this list.
131
    public ELEMENT removeLast() {
132
        if (this.size() <= 0) {
133
            throw new RuntimeException("La lista está vacía...");
134
        }
135
        ELEMENT item = this.tail.item;
136
        if (this.head.next == null) {
137
            this.head = this.tail = null;
138
        } else {
139
            this.tail = this.tail.prev;
140
            this.tail.next = null;
141
        }
142
        --this.count;
143
        return item;
144
    }
145
    //endregion
146
147
    //region Object Methods
148
149
    @Override
150
    public String toString() {
151
152
        if (this.size() <= 0) {
153
            return "";
154
        }
155
156
        // from https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/lang/StringBuilder.html
157
        StringBuilder sb = new StringBuilder();
158
159
        sb.append("[" + this.head.item.toString());
160
        for (Node<ELEMENT> skip = this.head.next; skip != null; skip = skip.next) {
161
            sb.append(", " + skip.item.toString());
162
        }
163
        sb.append("]");
164
165
        return sb.toString();
166
    }
167
    //endregion
168
169
    //region Iterable Methods
170
    @Override
171
    public Iterator<ELEMENT> iterator() {
172
        return new DoubleLinkedListIterator(this.head);
173
    }
174
175
    public class DoubleLinkedListIterator implements Iterator<ELEMENT> {
176
        private Node<ELEMENT> current;
177
178
        public DoubleLinkedListIterator(Node<ELEMENT> current) {
179
            this.current = current;
180
        }
181
182
        @Override
183
        public boolean hasNext() {
184
            return this.current != null;
185
        }
186
187
        @Override
188
        public ELEMENT next() {
189
            if (!this.hasNext()) {
190
                throw new RuntimeException("La lista está vacía...");
191
            }
192
            ELEMENT item = this.current.item;
193
            this.current = this.current.next;
194
            return item;
195
        }
196
    }
197
198
    public Iterator<ELEMENT> iteratorBack() {
199
        return new DoubleLinkedListIteratorBack(this.tail);
200
    }
201
202
    public class DoubleLinkedListIteratorBack implements Iterator<ELEMENT> {
203
        private Node<ELEMENT> current;
204
205
        public DoubleLinkedListIteratorBack(Node<ELEMENT> current) {
206
            this.current = current;
207
        }
208
209
        @Override
210
        public boolean hasNext() {
211
            return this.current != null;
212
        }
213
214
        @Override
215
        public ELEMENT next() {
216
            if (!this.hasNext()) {
217
                throw new RuntimeException("La lista está vacía...");
218
            }
219
            ELEMENT item = this.current.item;
220
            this.current = this.current.prev;
221
            return item;
222
        }
223
224
    }
225
226
    //endregion
227
228
}
229