public class DoubleLinkedList<T> {
public Node<T> head = null;
public Node<T> tail = null;
public class Node<T>{
T data;
Node<T> prev = null;
Node<T> next = null;
public Node(T data){
this.data = data;
}
}
public void addNode(T data) {
if (this.head == null) { // 노드가 존재하지 않는다면
this.head = new Node<T>(data); // 헤드에 새 노드를 생성
this.tail = this.head; // 노드가 하나 뿐이라 테일도 똑같이 헤드를 가리키게 한다.
} else { // 노드가 하나라도 존재할 때
Node<T> node = this.head; // 임시노드에 헤드를 가져오고
while ( node.next != null) { // 노드의 끝까지
node = node.next; // 다음 노드를 가져온다.
}
node.next = new Node<T>(data); // 노드의 끝에서 노드를 생성한다.
node.next.prev = node; // 새로 만든 노드의 이전 노드를 설정
this.tail = node.next; // 제일 끝 노드를 새로 생성 했으므로 테일을 재설정.
}
}
public void printAll() {
if (this.head != null) { // 헤드가 널이 아니어야 출력이 가능하다.
System.out.println(this.head.data); // 헤드의 데이터 부터 출력
Node<T> node = this.head; // 임시 노드에 헤드 넣기
while(node.next != null) { // 다음 노드가 없을 때까지 반복
node = node.next; // 다음 노드 설정
System.out.println(node.data); // 노드 데이터 출력
}
}
}
public T searchFromHead(T isData) {
if (this.head == null) { // 헤드가 널이면 노드가 하나도 없다.
return null; // 찾을 수 없기에 널 반환
} else {
Node<T> node = this.head; // 임시 노드에 헤드 넣기
while (node != null) { // 노드가 널이 아니면 반복
if ( node.data == isData) { // 노드의 데이터가 찾으려는 데이터와 같으면
return node.data; // 노드의 데이터를 반환
} else { // 그게 아니면
node = node.next; // 다음 노드 체크
}
}
return null; // 반복을 모두 돌고도 찾는 데이터가 없으면 널 반환
}
}
public T searchFromTail (T isData) {
if (this.head == null) { // 헤드가 널이면
return null; // 노드가 하나도 없으므로 널 반환
} else {
Node<T> node = this.tail; // 이번엔 테일에서 시작하기 때문에 테일 대입
while ( node != null) { // 노드가 널이 아니면 반복
if (node.data == isData) { // 노드의 데이터가 찾는 데이터라면
return node.data; // 그 노드의 데이터 반환
} else {
node = node.prev; // 이전 노드로
}
}
return null; // 반복을 전부 완료하고 없으면 널 반환
}
}
public boolean insertToFront ( T existedData, T addData) {
if (this.head == null) { // 헤드가 널이라면
this.head = new Node<T>(addData); // 헤드에 새로운 노드 생성
this.tail = this.head; // 노드가 하나이므로 테일로도 설정
return true; // 데이터 추가 성공이므로 true 반환
} else if ( this.head.data == existedData) { // 헤드의 데이터가 찾는 데이터일 때
Node<T> newHead = new Node<T>(addData); // 새로운 헤드에 새 노드를 만들어 대입
newHead.next = this.head; // 새 헤드의 다음 노드로 헤드 대입
this.head = newHead; // 헤드에 새 노드 대입
this.head.next.prev = this.head; // 다음 노드의 이전 노드로 헤드 대입
return true; // 데이터 추가 성공이므로 true 반환
} else { // 헤드가 존재하고 찾는 데이터가 헤드에 있지 않을 때
Node<T> node = this.head; // 노드에 헤드 대입
while ( node != null) { // 노드가 널이 아닐 때 반복
if ( node.data == existedData) { // 노드의 데이터가 찾는 데이터라면
Node<T> nodePrev = node.prev; // 노드의 이전 노드 가져옴
nodePrev.next = new Node<T>(addData); // 이전노드의 다음 노드로 새 노드 대입
nodePrev.next.next = node; // 이전 노드의 다음다음 즉 새 노드의 다음 노드 로 노드 대입
nodePrev.next.prev = nodePrev; // 새 노드의 이전 노드로 이전 노드 지정
node.prev = nodePrev.next; // 노드의 이전 노드로 새 노드 지정
return true; // 데이터 추가가 성공적이므로 true 반환
} else {
node = node.next; // 찾는 데이터가 아니라면 다음 노드 불러옴
}
}
return false; // 반복이 전부 종료 되더라도 못찾으면 false 반환
}
}
public boolean delNode(T isData) {
if ( this.head == null) { // 헤드가 널이면
return false; // 지울 수 있는게 없기에 false 반환
} else {
Node<T> node = this.head;
if (node.data == isData) { // 헤드의 데이터가 바로 지우려는 데이터일 때
this.head = this.head.next; // 헤드는 헤드의 다음으로 지정
this.head.prev = null; // 다음 헤드의 이전 노드는 널로 지정
return true; // 지움을 성공해서 true 반환
} else { // 헤드의 데이터가 지우려는 데이터가 아닐 때
while(node.next != null) { // 다음 노드가 널이 아니면 반복
if(node.next.data == isData) { // 다음 노드의 데이터가 지우려는 데이터일 때
Node<T> nodeTemp = node; // 임시 노드에 노드 저장
Node<T> nodeDel = nodeTemp.next; // 지우려는 노드는 다음 노드 이것도 저장
nodeTemp.next = nodeTemp.next.next; // 임시 노드의 다음노드를 다음다음 노드로 저장
if (nodeTemp.next != null) { // 임시노드의 다음노드가 있다면
nodeTemp.next.prev = nodeTemp; // 임시노드의 다음 노드의 이전노드를 임시노드로 저장
}
if (nodeDel == this.tail) { // 지우려는 노드가 테일 이었다면
this.tail = nodeTemp; // 테일 노드를 임시노드로 지정
}
return true;
} else { // 지우려는 노드의 데이터를 못찾았다면 다음 노드로 넘어감
node = node.next;
}
}
return false; // 반복을 다 돌고도 못찾았다면 false 반환.
}
}
}
public static void main(String[] args) {
// 테스트 코드
DoubleLinkedList<Integer> MyLinkedList = new DoubleLinkedList<Integer>();
MyLinkedList.addNode(1);
MyLinkedList.addNode(2);
MyLinkedList.addNode(3);
MyLinkedList.addNode(4);
MyLinkedList.addNode(5);
MyLinkedList.printAll();
System.out.println("----------------");
MyLinkedList.insertToFront(3, 2);
MyLinkedList.delNode(1);
MyLinkedList.delNode(2);
MyLinkedList.delNode(3);
MyLinkedList.delNode(4);
MyLinkedList.delNode(5);
MyLinkedList.printAll();
System.out.println("----------------");
MyLinkedList.insertToFront(6, 2);
MyLinkedList.insertToFront(1, 0);
MyLinkedList.printAll();
System.out.println("----------------");
MyLinkedList.addNode(6);
MyLinkedList.printAll();
}
}
댓글