[Computer Science] 이중연결리스트

• doubly linked list의 핵심은 노드와 노드가 서로 연결되어 있다는 점이다.
• 장점
  • '이중 연결 리스트'의 큰 장점은 양방향으로 연결되어 있기 때문에, 노드를 탐색하는 방향이 양쪽으로 가능하다는 것이다.
  • 단일연결리스트의 경우는 맨끝의 데이터를 가져올때, 순차적으로 처음노드(head)부터 탐색을 해야한다.
• 단점
  • 이전 노드를 지정하기 위한 변수를 하나 더 사용해야 한다.
  • 구현이 '단일연결리스트'에 비해 복잡하다.

 

public class DoublyLinkedList{

	private Node head;
	private Node tail;
	private int size;

	public DoublyLinkedList(){
		size = 0;
	}

	private class Node{
		private Node nextNode;
		private Node prevNode;
		private Object data;

		Node(Object data){
			this.data=data;
			this.nextNode=null;
			this.prevNode=null;
		}
	}
}

 

• 데이터 추가

 

 

 

public void addFirst(Object data) {
	Node newNode = new Node(data);

	if (head != null) {
	 // 기존 노드가 있음
	newNode.nextNode = head; 
	head.prevNode = newNode; 
	}

	head = newNode; 
	if (head.nextNode == null) {
	 tail = head;
	}
	size++; 
}

public void addLast(Object data) { 
	if (size == 0) { 
	addFirst(data); 
	} else { 
	Node newNode = new Node(data); 
	tail.nextNode = newNode; 
	newNode.prevNode = tail; 
	tail = newNode; 
	size++; 
	} 
}

public void add(int index, Object data) { 
	if (index == 0) { 
		addFirst(data); 
	} else if (index == size - 1) { 
		addLast(data); 
	} else { 
		Node newNode = new Node(data); 
		Node prevNode = getNode(index - 1); 
		Node nextNode = prevNode.nextNode; 

// 추가된 노드의 전후 설정 
		newNode.prevNode = prevNode; 
		newNode.nextNode = nextNode; 

// 이전 노드의 전후 설정 
		prevNode.nextNode = newNode; 

// 다음 노드의 전후 설정 
		nextNode.prevNode = newNode; 
		size++; 
	} 
}

• 데이터 지우기

 

public Object remove(int index) { 
	if(size == 0) { 
		return null; 
	} 
	if(index == 0) { 
		return removeFirst(); 
	}else if(index == size-1) { 
		return removeLast(); 
	}else { 
		Node removeNode = getNode(index); 
		Node prevNode = removeNode.prevNode; 
		Node nextNode = removeNode.nextNode; 

		// 이전 노드 전후 설정 
		prevNode.nextNode = nextNode; 

		// 다음 노드 전후 설정 
		nextNode.prevNode = prevNode; 
		size--; 
		return removeNode.data; 
	} 
}