이중 연결 리스트(Doubly Linked List)란?
단순 연결 리스트의 경우 노드는 다음 노드에 대한 참조만 가지고 있으므로 단방향으로 밖에 탐색을 하지 못한다.
이중 연결 리스트는 이를 보완하여 다음 노드뿐만 아니라 이전 노드의 참조까지 추가하여
양방향으로 탐색이 가능하도록 만들어 검색속도를 향상시킬 수 있는 방법을 제공한다.
package datastructure;
public class DoublyLinkedList_Rz {
class DoublyLinkedList{
private Node head;
private int size;
public DoublyLinkedList(){
head = new Node(null);
size = 0;
}
private class Node{
private Object data;
private Node prevNode;
private Node nextNode;
public Node(Object data){
this.data = data;
this.prevNode = null;
this.nextNode = null;
}
// index 위치에 있는 노드의 데이터를 반환한다.
public Object get(int index){
return getNode(index).data;
}
// 첫번째 위치에 있는 노드의 데이터를 반환한다.
public Object getFirst(){
return get(0);
}
// index 위치에 있는 노드를 반환한다.
private Node getNode(int index){
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("Index : " + index + "Size : " + size);
}
Node node = head;
// index 값이 리스트 size의 중간보다 앞에 있다면 앞에서부터 순차적으로 탐색한다.
if(index <= (size / 2)){
for(int i = 0; i <= index; i++){
node = node.nextNode;
}
} else{ // index 값이 리스트 size의 중간보다 뒤에 있다면 뒤에서부터 역으로 탐색한다.
for(int i = size; i > index; i--){
node = node.prevNode;
}
}
return node;
}
// 해당 데이터의 노드 위치를 반환한다.
public int getNodeIndex(Object obj){
Node node = head.nextNode;
for(int i = 0; i < size; i++){
if(obj.equals(node.data)){
return i;
}
node = node.nextNode;
}
return -1;
}
// 첫번째 위치에 노드를 삽입한다.
public void addFirst(Object data){
Node newNode = new Node(data);
newNode.nextNode = head.nextNode;
if(head.nextNode != null){ // 리스트가 비어있지 않다면
head.nextNode.prevNode = newNode;
} else{ // 리스트가 비어있다면
head.prevNode = newNode;
}
head.nextNode = newNode;
size++;
}
// 마지막 위치에 노드를 삽입한다.
public void addLast(Object data){
add(size, data);
}
// index 위치에 data를 삽입한다.
public void add(int index, Object data){
if(index == 0){
addFirst(data);
return;
}
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("Index : " + index + "Size : " + size);
}
Node newNode = new Node(data);
Node prevNode = getNode(index - 1);
Node nextNode = prevNode.nextNode;
prevNode.nextNode = newNode;
newNode.prevNode = prevNode;
newNode.nextNode = nextNode;
if(newNode.nextNode != null){ // 삽입 위치가 마지막이 아니라면
nextNode.prevNode = newNode;
} else{ // 삽입 위치가 마지막이라면
head.prevNode = newNode;
}
size++;
}
// 첫번째 노드를 제거하고 데이터를 반환한다.
public Object removeFirst(){
Node resultNode = getNode(0);
head.nextNode = resultNode.nextNode;
if(head.nextNode != null){ // 리스트가 비어있지 않을 경우
resultNode.nextNode.prevNode = null; // 두번째 노드가 가르키는 앞 노드는 없다.
} else{ // 리스트가 비어있을 경우
head.prevNode = null; // 헤드가 가르키는 마지막 노드는 없다.
}
size--;
return resultNode.data;
}
// index 위치의 노드를 제거하고 데이터를 반환한다.
public Object remove(int index){
if(index == 0){
return removeFirst();
}
if(index < 0 || index > size){
throw new IndexOutOfBoundsException("Index : " + index + "Size : " + size);
}
Node resultNode = getNode(index);
Node prevNode = resultNode.prevNode;
if(resultNode.nextNode != null){ // 삭제되는 노드의 위치가 마지막이 아니라면
Node nextNode = resultNode.nextNode;
prevNode.nextNode = nextNode;
nextNode.prevNode = prevNode;
} else{ // 삭제되는 노드의 위치가 마지막이라면
prevNode.nextNode = null;
head.prevNode = prevNode;
}
size--;
return resultNode.data;
}
// 마지막 노드를 제거하고 데이터를 반환한다.
public Object removeLast(){
return remove(size - 1);
}
// 리스트의 사이즈를 반환한다.
public int getSize(){
return size;
}
}
}
}
