[자료구조] 리스트_이중 연결 리스트(Doubly Linked List)

이중 연결 리스트(Doubly Linked List)

---

Linked List가 양방향으로 연결된 구조, 연결리스트의 단점을 개선한 구조

 

장점 : 탐색이 양쪽으로 가능

 

단점 : 메모리가 많이 사용된다

 

구조

---

구현

---

생성

public class DoublyLinkedList {
	private Node head; 	// 시작 위치
	private Node tail; 	// 끝 위치
	private int size = 0; 	// list 크기

	private class Node {
		private Object data; 	// data field, 노드 데이터
		private Node next; 	// Link field, 다음 노드 정보
		private Node prev; 	// 이전 노드 정보

		public Node(Object input) {  // 초기화
			this.data = input;
			this.next = null;
			this.prev = null;
		}

		public String toString() {
			return String.valueOf(this.data);
		}
	}
}

추가

< 맨 앞에 추가 >

public void addFirst(Object input) {
	Node newNode = new Node(input); // 노드 생성
	newNode.next = head;		// 새 노드의 Linked field에 head(다음노드) 지정
	if(head!=null) { 		// head가 존재한다면
		head.prev = newNode; 	// 헤드의 prev에 새 노드 지정
	}		
	head = newNode; 		// 헤드에 새 노드 지정
	size++;				// list 크기
	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;	// 마지막 노드에 다음 노드로 새 노드 지정
		newNode.prev = tail; 	// 새 노드의 prev에 tail 지정
		tail = newNode;		// 마지막 노드 갱신
		size++;
	}
}

 

<특정한 위치에 노드 추가>

public void add(int k, Object input) {
	if (k == 0) {			//첫 노드에 추가
		addFirst(input);
	} else {				
		Node temp1 = node(k - 1);	//temp1에 k번째 바로 전 노드를 지정
		Node temp2 = temp1.next;	//temp2에 k번째 노드 지정
		Node newNode = new Node(input); //새 노드 생성
		temp1.next = newNode;		//temp1의 다음 노드로 새 노드를 지정
		newNode.prev = temp1;		// 새 노드의 prev에 temp1 지정
		newNode.next = temp2;		//새 노드 다음 노드로 temp2 지정
		if (temp2 != null) {		// temp2가 존재한다면	
			temp2.prev = newNode;	// temp2 prev에 새 노드 지정
		}
		size++;
		if(newNode.next == null)	//다음 노드가 없을 때(마지막노드)
			tail = newNode;	
	}		
}

탐색

Node node(int index) {
	if(index < size/2) { 		//index가 (size/2)보다 작으면 처음부터 탐색
		Node x = head;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x;
	} else {			//index가 (size/2)보다 크면 마지막부터 탐색
		Node x= tail;
		for (int i = size-1; i > index; i--) {
			x = x.prev;
		}
		return x;
	}
}

삭제

<맨 앞 노드 삭제>

public Object removeFirst() {
	Node temp = head;		// temp 에 head(첫번째 노드) 지정
	head = head.next;		// head에 두번째 노드 지정
	Object returnData = temp.data;  // 삭제될 값을 리턴하기 위해 임시 변수에 넣음
	temp = null;			// 노드 삭제
	if(head != null) {		// head가 존재한다면
		head.prev = null;			
	}
	size--;
	
	return returnData;
}

 

<특정한 위치에 있는 노드 삭제>

public Object remove(int k) {
	if(k == 0) {	
		return removeFirst();
	}else {
		Node temp = node(k-1);			// k번째 앞 노드의 값을 temp에 지정
		Node todoDeleted = temp.next; 		// k번째 노드를 todoDeleted에 넣음
		temp.next = temp.next.next;		// k번째 뒷 노드를 temp의 다음 노드로 지정
		if (temp.next != null) {		// temp.next가 존재한다면
				temp.next.prev = temp;	// temp.next의 prev에 temp 지정
			}
		Object returnData = todoDeleted.data;
		if(todoDeleted == tail) {		// 삭제하는 노드가 마지막 노드일 때
			tail = temp;	
		}
		todoDeleted = null;	// 노드 삭제
		size--;
		
		return returnData;
	}		
}