[자료구조] 자바 반복자, 연결 리스트, 스택과 큐

https://www.youtube.com/playlist?list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk

Data Structures

 

Rob Edwards 교수님의 CS310 Data Structures in Java를 공부하고 정리한 내용입니다.

 

부스트 코스 자바로 구현하고 배우는 자료구조에서도 학습할 수 있습니다.

 

이번 포스팅에서는 반복자를 내부에서 어떻게 구현하는지를 알아보고, 이중 연결 리스트, 원형 연결 리스트, 스택과 큐에 대해 간단히 소개하려합니다.

---

1-11. 반복자

배열의 경우, 다음과 같이 for-each문을 이용해서 간단하게 반복문을 구현할 수 있다.

int arr[] = {1,2,3,4,5};
for (int i=0; i<arr.length; i++) {
    doSomething();
}
for (int x : arr) {
    doSomething();
}

 

우리가 사용하고 싶은 다른 자료구조에서도 위처럼 for-each문을 사용하려면 iterable<E> 인터페이스를 구현해야한다. 

 

public Iterator<E> iterator() {
    return new IteratorHelper();
}

public class LinkedList<E> implements ListI<E> {
    class IteratorHelper implements Iterator<E> {
        Node<E> index;
        public IteratorHelper() {
            index = head;
        }
        public boolean hasNext() {
            return (index != null);
        }
        public E next() {
            if (!hasNext())
                throw new NoSuchElementException();
            E val = index.data;
            index = index.next;
            return val;
        }
    }
}

 

hasNext(), Next()

예를 들어 LinkedList 1 2 3 4가 있다고 하자.

 

포인터가 2에 있다면 hasNext를 실행했을 때 true를 반환해야하고,  next를 실행했을 때 3으로 이동한다.

 

pointer가 4에 있다면 null로 이동할 것이다. pointer가 4에 있다면 hasNext를 실행했을 때 false를 반환해야 한다.

 

Linked List의 마지막인지 확인하려면 임시 포인터가 null을 가리키는지 보면 된다.

---

1-12. 이중연결리스트

이중연결리스트로 removeLast 등 메서드에서 시간복잡도를 O(n)에서 O(1)로 줄일 수 있다.

 

이전에 작성했던 LinkedList의 문제점은 tail이 있어도 removeLast등을 사용할 때 head부터 탐색을 시작하기 때문에 시간복잡도가 O(n)이라는 것이다.

 

 

이중연결리스트는 next뿐만 아니라 prev를 가지고 있는데, prev는 이전 노드를 가리킨다.

 

E tmp = tail.data;를 사용해서 tail을 이동시키기 전에 임시 포인터가 마지막 요소인 C를 가리키게 한다.

마지막 요소를 삭제하려면 tail.prev.next = null;을 작성해서 B가 C를 가리키지 않게 하면된다. 그리고 tail = tail.prev;를 사용해서 tail을 이전 요소인 B로 이동시킨다. 그리고 tmp를 반환한다.

 

이전의 연결 리스트와 다르게 head부터 순서대로 마지막 요소를 탐색하지 않기 때문에 시간복잡도가 O(n)에서 O(1)로 줄어들었다.

 

 

마지막 요소를 삭제하기는 편하지만 단점은 prev가 추가됐기 때문에 많은 메모리 공간이 필요하고, 새로운 노드를 삽입하고 삭제할 때 연산이 더 복잡해진다는 것이다.

---

1-12. 원형 연결 리스트

원형 연결리스트는 아래와 같이 마지막 노드가 처음 노드를 가리키는 연결리스트이다. 

 

 

tail 포인터를 사용했을 때, head를 가리킨다면 시간복잡도 O(1)로 원형 연결 리스트인지 확인할 수 있다.

---

2-1. 스택과 큐

스택과 큐를 구현하는데, 연결 리스트를 사용하는 이유

배열에는 첫 부분을 추가하거나 제거할 때, 요소들을 하나씩 뒤로 옮기거나 앞으로 옮겨야 해서 시간복잡도가 O(n)이다.  그래서 배열을 스택과 큐를 구현하는데 사용하지 않는다. 대신 그동안 학습한 Linked List를 사용하는데, 앞에서 살펴봤듯이 리스트의 첫 부분을 제거하거나 추가할 때 시간복잡도가 O(1)이기 때문에 효율적으로 스택과 큐를 구현할 수 있다.

배열로 스택을 구현할 때

스택은 Last in First Out으로 나중에 들어온 원소가 제일 먼저 나가는 자료구조이다.

배열의 경우 addLast와 removeLast를 사용하는데 이 때 O(1)의 시간복잡도를 갖는다.

배열로 큐를 구현할 때

큐는 First in First Out으로 처음 들어온 원소가 제일 먼저 나가는 자료구조이다.

이 때, addFirst와 removeLast 혹은 addLast와 removeFirst를 사용한다.

addFirst와 removeLast를 사용할 때는, 추가할 때 O(n), 제거할 때 O(1)의 시간복잡도를 가지고

addLast와 removeFirst를 사용할 때는, 추가할 때 O(1), 제거할 때 O(n)의 시간복잡도를 갖는다.