- Double Linked List 방식을 사용
- 구현할 method
- Add 메서드:
- addFirst(E element) - 맨 앞에 추가
- addLast(E element) - 맨 뒤에 추가
- add(int index, E element) - 지정 위치에 추가
- Remove 메서드:
- removeFirst() - 첫 노드 삭제
- removeLast() - 마지막 노드 삭제
- remove(int index) - 인덱스로 삭제
- remove(Object o) - 특정 값을 가진 첫 노드 삭제 ( 커스텀 해도 좋음)
- get(int index) - 노드 탐색의 기본
- contains(Object o) - 전체 순회
- size() - 리스트 관리의 기본
- clear() - 전체 노드 삭제 처리
package linkedList;
import java.util.NoSuchElementException;
public class MyLinkedList<T> {
class Node<T> {
Node<T> prev;
T data;
Node<T> next;
public Node(Node<T> prev, T data, Node<T> next) {
this.prev = prev;
this.data = data;
this.next = next;
}
}
private int size = 0;
private Node<T> first;
private Node<T> last;
public MyLinkedList() {
}
public Node<T> get(int index) {
if (index < size / 2) {
Node<T> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
Node<T> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
public void addFirst(T data) {
Node<T> f = first;
Node<T> newNode = new Node<>(null, data, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}
public void addLast(T data) {
Node<T> l = last;
Node<T> newNode = new Node<>(l, data, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}
public void add(int index, T data) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException();
if (index == size) {
addLast(data);
} else if (index == 0) {
addFirst(data);
} else {
Node<T> target = get(index);
Node<T> newNode = new Node<>(target.prev, data, target);
target.prev.next = newNode;
target.prev = newNode;
size++;
}
}
public void removeFirst() {
if (size == 0)
throw new NoSuchElementException();
Node<T> f = first;
first = f.next;
f.data = null;
f.next = null;
if (first != null)
first.prev = null;
else
last = null;
size--;
}
public void removeLast() {
if (size == 0)
throw new NoSuchElementException();
Node<T> l = last;
last = l.prev;
l.data = null;
l.prev = null;
if (last != null)
last.next = null;
else
first = null;
size--;
}
public void remove(int index) {
if (index >= size || index < 0)
throw new IndexOutOfBoundsException();
if (index == size - 1) {
removeLast();
} else if (index == 0) {
removeFirst();
} else {
Node<T> target = get(index);
target.prev.next = target.next;
target.next.prev = target.prev;
target.next = null;
target.prev = null;
target.data = null;
size--;
}
}
public int remove(T data) {
Node<T> current = first;
int cnt = 0;
while (current != null) {
Node<T> nextNode = current.next;
if ((data == null && current.data == null) || (data != null && data.equals(current.data))) {
if (current == first) {
removeFirst();
} else if (current == last) {
removeLast();
} else {
current.prev.next = current.next;
current.next.prev = current.prev;
current.data = null;
current.next = null;
current.prev = null;
size--;
}
cnt++;
}
current = nextNode;
}
return cnt;
}
public int contains(T data) {
Node<T> current = first;
int cnt = 0;
while (current != null) {
if ((data == null && current.data == null) || (data != null && data.equals(current.data))) {
cnt++;
}
current = current.next;
}
return cnt;
}
public int size() {
return size;
}
public void clear() {
for (Node<T> x = first; x != null;) {
Node<T> next = x.next;
x.prev = null;
x.next = null;
x.data = null;
x = next;
}
first = null;
last = null;
size = 0;
}
@Override
public String toString() {
if (size == 0) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append('[');
Node<T> current = first;
while (current != null) {
sb.append(current.data);
if (current.next != null) {
sb.append(", ");
}
current = current.next;
}
sb.append(']');
return sb.toString();
}
}