public class LinkedList {
private Node head;
private Node tail;
private int size = 0;
private class Node {
private Object data;
private Node next;
// 변수타입을 가지고 있어야함
public Node(Object input) {
this.data = input;
this.next = null;
}
public String toString() {
return String.valueOf(this.data);
}
}
// 머리에다가 추
public void addFirst(Object input) {
Node newNode = new Node(input);
newNode.next = head;
head = newNode;// 방금 생성한 노드를 head로
size++;
// 다음노드가 존재하지 않는다는
if (head.next == null) {
tail = head;
}
}
public void addLast(Object input) {
Node newNode = new Node(input);
if (size == 0) {
addFirst(input);
} else {
tail.next = newNode;
tail = newNode;
size++;
}
}
// 내부적으로 사용할것 (test를 위해 public)
Node node(int index) {
// 첫번째 노드를 찾아오는 것이고 그게 헤드이다.
Node x = head;
// 다음 노드들을 가지고 오기 위해서 next를 인덱스만큼 반복
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
public void add(int k, Object input) {
if (k == 0) {
addFirst(input);
} else {
// 추가시키지 이전 노드를 알고있어야함
Node temp1 = node(k - 1);
// 밀어질 노드에 대한 정보
Node temp2 = temp1.next;
Node newNode = new Node(input);
temp1.next = newNode;
newNode.next = temp2;
size++;
// 뒤에 널이면 테일로 바준닷.
if (newNode.next == null) {
tail = newNode;
}
}
}
public String toString() {
if (head == null) {
return "[]";
}
Node temp = head;
String str = "[";
while (temp.next != null) {
str += temp.data + ",";
temp = temp.next;
}
str += temp.data;
return str + "]";
}
// 자바에서는 컬렉션 프레임웍은 삭제된 노드의 값을 리턴해주게된다.
public Object removeFirst() {
Node temp = head;
head = head.next;
Object returnData = temp.data;
temp = null;
size--;
return returnData;
}
// 노드 삭제하기
public Object remove(int k) {
if (k == 0) {
return removeFirst();
}
Node temp = node(k - 1);
Node todoDeleted = temp.next;
temp.next = temp.next.next;
Object returnData = todoDeleted.data;
if (todoDeleted == tail) {
tail = temp;
}
todoDeleted = null;
size--;
return returnData;
}
// 마지막 노드 삭제 테일만 지우면 이것저것 효과가 없어진닷;
public Object removeLast() {
return remove(size - 1);
}
// 사이즈 호출하기
public int size() {
return size;
}
// 특정한 위치의 데이터 가져오기
public Object get(int k) {
Node temp = node(k);
return temp.data;
}
public int indexOf(Object data) {
Node temp = head;
int index = 0;
while (temp.data != data) {
temp = temp.next;
index++;
if (temp == null) {
return -1;
}
}
return index;
}
public ListIterator listIterator() {
return new ListIterator();
}
public class ListIterator {
private Node next;
private Node lastReturned;
// 몇번째 있는가 알필요가 있고, hasNext할때 필
private int nextIndex;
ListIterator() {
next = head;
}
public Object next() {
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.data;
}
public boolean hasNext() {
return nextIndex < size();
}
public void add(Object input) {
Node newNode = new Node(input);
if (lastReturned == null) {
head = newNode;
newNode.next = next;
} else {
lastReturned.next = newNode;
newNode.next = next;
}
lastReturned = newNode;
nextIndex++;
size++;
}
public void remove() {
if(nextIndex == 0) {
throw new IllegalStateException();
}
//비효율적이다. 노드를 찾았는데또 찾음!;
LinkedList.this.remove(nextIndex-1);
nextIndex--;
}
}
}