Data Structure (자료구조)

비전공자는 도전해볼 수 있고, 전공자는 쉽게 배울 수 있는 데이터 스트럭쳐 수업

Data Structure (자료구조) 비전공자는 도전해볼 수 있고, 전공자는 쉽게 배울 수 있는 데이터 스트럭쳐 수업

Doubly linked list - Java 구현

이중 연결 리스트는 단순 연결 리스트를 기반으로 약간의 변형을 가한 것이기 때문에 단순 연결 리스트의 소스 코드를 수정하는 방법으로 접근하면 됩니다. 여기서는 차이점을 중심으로 알아보도록 하겠습니다.

클래스

DoublyLinkedList.java 

package list.doublylinkedlist.implementation;

public class DoublyLinkedList {
    // 첫번째 노드를 가리키는 필드
	private Node head;
	private Node tail;
	private int size = 0;
}

노드

노드에는 이전 노드에 대한 부분이 추가 됩니다.

private class Node {
	// 데이터가 저장될 필드
	private Object data;
	// 다음 노드를 가리키는 필드
	private Node next;
	private Node prev;

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

	// 노드의 내용을 쉽게 출력해서 확인해볼 수 있는 기능
	public String toString() {
		return String.valueOf(this.data);
	}
}

아래는 linked list 대비 doubly linked list에서 변경된 부분을 보여주고 있습니다. 붉은색으로 표시된 부분이 추가된 부분입니다.

DoublyLinkedList.java VS LinkedList.java

추가

시작 위치에 추가

public void addFirst(Object input) {
	// 노드를 생성합니다.
	Node newNode = new Node(input);
	// 새로운 노드의 다음 노드로 헤드를 지정합니다.
	newNode.next = head;
	// 기존에 노드가 있었다면 현재 헤드의 이전 노드로 새로운 노드를 지정합니다.
	if (head != null)
		head.prev = newNode;
	// 헤드로 새로운 노드를 지정합니다.
	head = newNode;
	size++;
	if (head.next == null) {
		tail = head;
	}
}

 head 앞에 새로운 노드가 위치하게 되기 때문에 head의 이전 값으로 새로운 노드를 지정하는 부분이 추가 되었습니다.

끝에 추가

public void addLast(Object input) {
	// 노드를 생성합니다.
	Node newNode = new Node(input);
	// 리스트의 노드가 없다면 첫번째 노드를 추가하는 메소드를 사용합니다.
	if (size == 0) {
		addFirst(input);
	} else {
		// tail의 다음 노드로 생성한 노드를 지정합니다.
		tail.next = newNode;
		// 새로운 노드의 이전 노드로 tail을 지정합니다.
		newNode.prev = tail;
		// 마지막 노드를 갱신합니다.
		tail = newNode;
		// 엘리먼트의 개수를 1 증가 시킵니다.
		size++;
	}
}

 

특정 위치에 추가

public void add(int k, Object input) {
	// 만약 k가 0이라면 첫번째 노드에 추가하는 것이기 때문에 addFirst를 사용합니다.
	if (k == 0) {
		addFirst(input);
	} else {
		Node temp1 = node(k - 1);
		// k 번째 노드를 temp2로 지정합니다.
		Node temp2 = temp1.next;
		// 새로운 노드를 생성합니다.
		Node newNode = new Node(input);
		// temp1의 다음 노드로 새로운 노드를 지정합니다.
		temp1.next = newNode;
		// 새로운 노드의 다음 노드로 temp2를 지정합니다.
		newNode.next = temp2;
		// temp2의 이전 노드로 새로운 노드를 지정합니다.
		if (temp2 != null)
			temp2.prev = newNode;
		// 새로운 노드의 이전 노드로 temp1을 지정합니다.
		newNode.prev = temp1;
		size++;
		// 새로운 노드의 다음 노드가 없다면 새로운 노드가 마지막 노드이기 때문에 tail로 지정합니다.
		if (newNode.next == null) {
			tail = newNode;
		}
	}
}

위의 코드를 보면 temp1을 지정하는 로직이 node(k-1)로 변경된 것을 볼 수 있습니다. 노드 탐색 작업이 빈번한 작업이기 때문에 별도의 메소드로 분리시켰습니다. 이 부분은 곧 살펴보겠습니다. 그 외의 코드 상의 변화는 앞뒤 노드를 연결해주는 것과 관련된 부분입니다. 그림을 그려서 관계를 따라그려보면 어렵지 않게 파악할 수 있는 내용입니다.

노드 찾기

아래는 노드를 찾는 작업을 메소드화시킨 것입니다.

Node node(int index) {
	// 노드의 인덱스가 전체 노드 수의 반보다 큰지 작은지 계산
	if (index < size / 2) {
		// head부터 next를 이용해서 인덱스에 해당하는 노드를 찾습니다.
		Node x = head;
		for (int i = 0; i < index; i++)
			x = x.next;
		return x;
	} else {
		// tail부터 prev를 이용해서 인덱스에 해당하는 노드를 찾습니다.
		Node x = tail;
		for (int i = size - 1; i > index; i--)
			x = x.prev;
		return x;
	}
}

위의 코드는 중요한 내용을 담고 있습니다. 이중 연결 리스트의 장점이 담겨있기 때문입니다.

위의 그림과 같이 리스트의 노드가 6개라고 했을 때 get의 인자로 전달된 인덱스가 2(30의 인덱스)이하라면 head부터 next를 이용해서 탐색을 합니다. 인덱스가 3이상이라면 tail부터 prev를 이용해서 탐색을 할 수 있습니다. 즉 인덱스의 위치에 따라서 탐색 방향을 달리 할 수 있습니다. 덕분에 탐색 시간을 두배로 향상시킬 수 있습니다. 이것이 양방향으로 연결을 했을 때의 효용입니다.

삭제

처음 노드 삭제

public Object removeFirst() {
	// 첫번째 노드를 temp로 지정하고 head의 값을 두번째 노드로 변경합니다.
	Node temp = head;
	head = temp.next;
	// 데이터를 삭제하기 전에 리턴할 값을 임시 변수에 담습니다.
	Object returnData = temp.data;
	temp = null;
	// 리스트 내에 노드가 있다면 head의 이전 노드를 null로 지정합니다.
	if (head != null)
		head.prev = null;
	size--;
	return returnData;
}

 

 특정 위치 노드 삭제

public Object remove(int k) {
	if (k == 0)
		return removeFirst();
	// k-1번째 노드를 temp로 지정합니다.
	Node temp = node(k - 1);
	// temp.next를 삭제하기 전에 todoDeleted 변수에 보관합니다.
	Node todoDeleted = temp.next;
	// 삭제 대상 노드를 연결에서 분리합니다.
	temp.next = temp.next.next;
	if (temp.next != null) {
		// 삭제할 노드의 전후 노드를 연결합니다.
		temp.next.prev = temp;
	}
	// 삭제된 노드의 데이터를 리턴하기 위해서 returnData에 데이터를 저장합니다.
	Object returnData = todoDeleted.data;
	// 삭제된 노드가 tail이었다면 tail을 이전 노드를 tail로 지정합니다.
	if (todoDeleted == tail) {
		tail = temp;
	}
	// cur.next를 삭제 합니다.
	todoDeleted = null;
	size--;
	return returnData;
}

 

마지막 노드 삭제

public Object removeLast() {
	return remove(size - 1);
}

 인덱스로 엘리먼트 가져오기

public Object get(int k) {
	Node temp = node(k);
	return temp.data;
}

탐색

다음 코드는 특정 데이터가 저장된 인덱스를 알아내는 방법입니다.

public int indexOf(Object data) {
	// 탐색 대상이 되는 노드를 temp로 지정합니다.
	Node temp = head;
	// 탐색 대상이 몇번째 엘리먼트에 있는지를 의미하는 변수로 index를 사용합니다.
	int index = 0;
	// 탐색 값과 탐색 대상의 값을 비교합니다.
	while (temp.data != data) {
		temp = temp.next;
		index++;
		// temp의 값이 null이라는 것은 더 이상 탐색 대상이 없다는 것을 의미합니다.이 때 -1을 리턴합니다.
		if (temp == null)
			return -1;
	}
	// 탐색 대상을 찾았다면 대상의 인덱스 값을 리턴합니다.
	return index;
}

반복

반복자(iterator)를 이용해서 순차적으로 노드를 탐색하는 방법은 Linked list에서 이미 알아봤습니다. 그런데 doubly linked list는 반복과 관련해서 중요한 차이가 있습니다. 바로 탐색 방향을 자유롭게 변경할 수 있다는 것입니다. 기존의 iterator 대비 3개의 메소드를 더 추가하겠습니다.

이전 노드 탐색

이중 연결 리스트의 기본적인 클래스 골격은 아래와 같습니다. next는 다음번 리턴 할 노드를 가르키고, lastReturned는 마지막으로 리턴된 노드를 가르킵니다. lastReturned는 next를 한칸 뒤에서 따라다닙니다. nextIndex는 next를 호출했을 때 다음 번 리턴될 노드의 인덱스 값을 의미합니다.

public class ListIterator {
	private Node lastReturned;
	private Node next;
	private int nextIndex;
    ListIterator() {
		next = head;
		nextIndex = 0;
	}
}

이중 연결 리스트는 next와 prev를 가지고 있기 때문에 탐색의 방향을 원하는데로 지정할 수 있습니다.

 

// 본 메소드를 호출하면 cursor의 참조값이 기존 cursor.next로 변경됩니다.
public Object next() {
	lastReturned = next;
	next = next.next;
	nextIndex++;
	return lastReturned.data;
}

// cursor의 값이 없다면 다시 말해서 더 이상 next를 통해서 가져올 노드가 없다면 false를 리턴합니다.
// 이를 통해서 next를 호출해도 되는지를 사전에 판단할 수 있습니다.
public boolean hasNext() {
	return nextIndex < size();
}

public boolean hasPrevious() {
	return nextIndex > 0;
}

public Object previous() {
	if (next == null) {
		lastReturned = next = tail;
	} else {
		lastReturned = next = next.prev;
	}
	nextIndex--;
	return lastReturned.data;
}

 

다음은 탐색 과정에서 노드의 삭제, 추가와 관련된 작업을 구현한 코드입니다.

public void add(Object input) {
	Node newNode = new Node(input);
	if (lastReturned == null) {
		head = newNode;
		newNode.next = next;
	} else {
		lastReturned.next = newNode;
		newNode.prev = lastReturned;
		if (next != null) {
			newNode.next = next;
			next.prev = newNode;
		} else {
			tail = newNode;
		}
	}
	lastReturned = newNode;
	nextIndex++;
	size++;
}

 

public void remove() {
	if (nextIndex == 0) {
		throw new IllegalStateException();
	}
	Node n = lastReturned.next;
	Node p = lastReturned.prev;

	if (p == null) {
		head = n;
		head.prev = null;
		lastReturned = null;
	} else {
		p.next = next;
		lastReturned.prev = null;
	}

	if (n == null) {
		tail = p;
		tail.next = null;
	} else {
		n.prev = p;
	}

	if (next == null) {
		lastReturned = tail;
	} else {
		lastReturned = next.prev;
	}

	size--;
	nextIndex--;

}

전체코드

아래는 전체 코드입니다.

package list.doublylinkedlist.implementation;

public class DoublyLinkedList {
    // 첫번째 노드를 가리키는 필드
	private Node head;
	private Node tail;
	private int size = 0;

	private class Node {
		// 데이터가 저장될 필드
		private Object data;
		// 다음 노드를 가리키는 필드
		private Node next;
		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;
		// 기존에 노드가 있었다면 현재 헤드의 이전 노드로 새로운 노드를 지정합니다.
		if (head != null)
			head.prev = newNode;
		// 헤드로 새로운 노드를 지정합니다.
		head = newNode;
		size++;
		if (head.next == null) {
			tail = head;
		}
	}

	public void addLast(Object input) {
		// 노드를 생성합니다.
		Node newNode = new Node(input);
		// 리스트의 노드가 없다면 첫번째 노드를 추가하는 메소드를 사용합니다.
		if (size == 0) {
			addFirst(input);
		} else {
			// tail의 다음 노드로 생성한 노드를 지정합니다.
			tail.next = newNode;
			// 새로운 노드의 이전 노드로 tail을 지정합니다.
			newNode.prev = tail;
			// 마지막 노드를 갱신합니다.
			tail = newNode;
			// 엘리먼트의 개수를 1 증가 시킵니다.
			size++;
		}
	}

	Node node(int index) {
		// 노드의 인덱스가 전체 노드 수의 반보다 큰지 작은지 계산
		if (index < size / 2) {
			// head부터 next를 이용해서 인덱스에 해당하는 노드를 찾습니다.
			Node x = head;
			for (int i = 0; i < index; i++)
				x = x.next;
			return x;
		} else {
			// tail부터 prev를 이용해서 인덱스에 해당하는 노드를 찾습니다.
			Node x = tail;
			for (int i = size - 1; i > index; i--)
				x = x.prev;
			return x;
		}
	}

	public void add(int k, Object input) {
		// 만약 k가 0이라면 첫번째 노드에 추가하는 것이기 때문에 addFirst를 사용합니다.
		if (k == 0) {
			addFirst(input);
		} else {
			Node temp1 = node(k - 1);
			// k 번째 노드를 temp2로 지정합니다.
			Node temp2 = temp1.next;
			// 새로운 노드를 생성합니다.
			Node newNode = new Node(input);
			// temp1의 다음 노드로 새로운 노드를 지정합니다.
			temp1.next = newNode;
			// 새로운 노드의 다음 노드로 temp2를 지정합니다.
			newNode.next = temp2;
			// temp2의 이전 노드로 새로운 노드를 지정합니다.
			if (temp2 != null)
				temp2.prev = newNode;
			// 새로운 노드의 이전 노드로 temp1을 지정합니다.
			newNode.prev = temp1;
			size++;
			// 새로운 노드의 다음 노드가 없다면 새로운 노드가 마지막 노드이기 때문에 tail로 지정합니다.
			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() {
		// 첫번째 노드를 temp로 지정하고 head의 값을 두번째 노드로 변경합니다.
		Node temp = head;
		head = temp.next;
		// 데이터를 삭제하기 전에 리턴할 값을 임시 변수에 담습니다.
		Object returnData = temp.data;
		temp = null;
		// 리스트 내에 노드가 있다면 head의 이전 노드를 null로 지정합니다.
		if (head != null)
			head.prev = null;
		size--;
		return returnData;
	}

	public Object remove(int k) {
		if (k == 0)
			return removeFirst();
		// k-1번째 노드를 temp로 지정합니다.
		Node temp = node(k - 1);
		// temp.next를 삭제하기 전에 todoDeleted 변수에 보관합니다.
		Node todoDeleted = temp.next;
		// 삭제 대상 노드를 연결에서 분리합니다.
		temp.next = temp.next.next;
		if (temp.next != null) {
			// 삭제할 노드의 전후 노드를 연결합니다.
			temp.next.prev = temp;
		}
		// 삭제된 노드의 데이터를 리턴하기 위해서 returnData에 데이터를 저장합니다.
		Object returnData = todoDeleted.data;
		// 삭제된 노드가 tail이었다면 tail을 이전 노드를 tail로 지정합니다.
		if (todoDeleted == tail) {
			tail = temp;
		}
		// cur.next를 삭제 합니다.
		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) {
		// 탐색 대상이 되는 노드를 temp로 지정합니다.
		Node temp = head;
		// 탐색 대상이 몇번째 엘리먼트에 있는지를 의미하는 변수로 index를 사용합니다.
		int index = 0;
		// 탐색 값과 탐색 대상의 값을 비교합니다.
		while (temp.data != data) {
			temp = temp.next;
			index++;
			// temp의 값이 null이라는 것은 더 이상 탐색 대상이 없다는 것을 의미합니다.이 때 -1을 리턴합니다.
			if (temp == null)
				return -1;
		}
		// 탐색 대상을 찾았다면 대상의 인덱스 값을 리턴합니다.
		return index;
	}

	// 반복자를 생성해서 리턴해줍니다.
	public ListIterator listIterator() {
		return new ListIterator();
	}

	public class ListIterator {
		private Node lastReturned;
		private Node next;
		private int nextIndex;

		ListIterator() {
			next = head;
			nextIndex = 0;
		}

		// 본 메소드를 호출하면 cursor의 참조값이 기존 cursor.next로 변경됩니다.
		public Object next() {
			lastReturned = next;
			next = next.next;
			nextIndex++;
			return lastReturned.data;
		}

		// cursor의 값이 없다면 다시 말해서 더 이상 next를 통해서 가져올 노드가 없다면 false를 리턴합니다.
		// 이를 통해서 next를 호출해도 되는지를 사전에 판단할 수 있습니다.
		public boolean hasNext() {
			return nextIndex < size();
		}

		public boolean hasPrevious() {
			return nextIndex > 0;
		}

		public Object previous() {
			if (next == null) {
				lastReturned = next = tail;
			} else {
				lastReturned = next = next.prev;
			}
			nextIndex--;
			return lastReturned.data;
		}

		public void add(Object input) {
			Node newNode = new Node(input);
			if (lastReturned == null) {
				head = newNode;
				newNode.next = next;
			} else {
				lastReturned.next = newNode;
				newNode.prev = lastReturned;
				if (next != null) {
					newNode.next = next;
					next.prev = newNode;
				} else {
					tail = newNode;
				}
			}
			lastReturned = newNode;
			nextIndex++;
			size++;
		}

		public void remove() {
			if (nextIndex == 0) {
				throw new IllegalStateException();
			}
			Node n = lastReturned.next;
			Node p = lastReturned.prev;

			if (p == null) {
				head = n;
				head.prev = null;
				lastReturned = null;
			} else {
				p.next = next;
				lastReturned.prev = null;
			}

			if (n == null) {
				tail = p;
				tail.next = null;
			} else {
				n.prev = p;
			}

			if (next == null) {
				lastReturned = tail;
			} else {
				lastReturned = next.prev;
			}

			size--;
			nextIndex--;

		}
	}

}

 

댓글

댓글 본문
  1. 빵승
    비전공 출신인 제게 정말 유익한 강의였습니다.
    감사합니다.

    ps. 강좌가 더 개설되었으면 정말 좋겠습니다!
  2. Taesoo Lee
    lastReturned = next.prev;
    이부분에서 없애주니까 또해줄필요없는거같네요
    대화보기
    • Taesoo Lee
      아쉽습니다..정말 더 자료구조를 끝까지해주셨으면 얼마나좋았을까요..
    • 익오잉
      이고잉님 자바 완강하고 자료구조 수업 듣고있습니다만, 이 밑에 추가강의는 언제쯤연재해주시나요?ㅠㅠ 여기서끝이라니 매우 아쉽습니다....
    • 넘나어려워요
      Iterator에서 next()하고나서 바로 previous()하는 순간부터 꼬이기 시작하는것 같습니다.
      lastReturned와 next가 다르다가 같아지니까 으......... 복잡하네요 너무 어렵다 ㅎㅎ
    • 극호
      이고잉님.. 대학교 강의 듣고 있는 21살 대학생이에요
      다름이 아니라 사랑합니다.(급고백) ♥
    • 레미렘
      안녕하세요 이고잉님 수업 너무나 잘 듣고 있습니다. 좋은 강의 제작해주셔서 너무 감사합니다.
      그리고 TREE나 큐도 제작 계획이 있으신지 궁금합니다
    • 파파파파퍄
      안녕하세요. 좋은 자료 제공해주셔서 감사합니다.
      그런데 이번 더블 링크드 리스트에서는 오류가 조금 있는 것 같아서 이렇게 댓글 남깁니다.
      이터레이터의 경우 next()로 진행하다가 prev()로 뒤로 가게 되면 lastReturned와 next가 같은 노드를 가리키게 됩니다. 이 때 add나 remove를 호출할 경우, 그 함수들은 lastReturned와 next가 다른 노드를 가리키는 경우를 기준으로 작성되었기 때문에 오류가 나는 것 같습니다. 그 부분에 작은 오류가 있는 것 같습니다.
    • 얼관
      이터레이터의 리무브 메서드에서 p==null이 아닐때요
      p.next = next;
      lastReturned.prev = null;
      이렇게 지우려는 노드의 앞에있는 연결은 서로 끊어줬는데
      뒤에있는건 왜 n.prev = p; 이것만 하고 lastReturned.next= null;은 안하나요?
    • SungJin Lee
      정말 감사합니다.
    • SpringShade
      좋은 자료 잘보고 갑니다!
    • gorgona
      안녕하세요. 강의 잘 보고 있습니다. 정말 쉽게 설명해주셔서 이해하기가 편하네요.

      다름이 아니라,
      Iterator add 동영상에서
      첫번째 위치에 노드를 집어넣을 때의 next.prev = newNode로 해주는 과정이 빠진 듯 합니다.
      동영상대로 하면, 첫번째 위치에 집어넣은 새로운 노드를 가리키는 다음 노드의 previous가 없을 거 같습니다.
    • egoing
      조언 감사합니다. 반영했습니다. ^^
      대화보기
      • Joshua
        감사합니다.. 늘 잘 듣고 있어요.. ^^

        remove() 메소드에 작은 버그가 있네요
        지우려고 하는 인덱스 값으로 마지막 index가 전달된 경우
        즉, k = size-1인 경우
        temp.next.prev = temp; <== 이 행에서 exception이 나는군요

        if(todoDeleted == tail) 문의 else 문 안으로 넣으면 괜찮을 것 같습니다.
      • 유지연
        목소리 진짜 좋으시고 멋지세요 그래서 집중이 더 잘되는 듯; 감사히 잘 듣고 있습니다
      버전 관리
      egoing@gmail.com
      현재 버전
      선택 버전
      graphittie 자세히 보기