데이터 구조와 알고리즘 6장 1

트리란 무엇인가?
트리는 연결 리스트와 유사한 데이터 구조이다. 하지만 각 노드가 선형적으로 다른 노드를 가리키는 게 아니라 각 노드가 여러 개의 노드를 가리킨다. 트리는 비선형적 데이터 구조의 한 예이다. 트리 구조는 구조의 계층적 속성을 그래프의 형태로 나타내는 방법이다.
// 항목의 순서는 중요하지 않다.

 - 용어 설명
1. 트리의 뿌리는 부모가 없는 노드이다. 트리에는 최대 한 개의 뿌리 노드가 있을 수 있다.(A)
2. 간선(edge)은 부모로부터 자식에게 이어지는 연결 선을 뜻한다.(모든 선)
3. 자식이 없는 노드를 잎(leaf) 노드라고 한다(E, I, J, K, I)
4. 같은 부모를 가진 자식들을 형제(sibling)라고 한다.(B, C, D는 A를 부모로 하는 형제 노드들이고 E, F는 B를 부모로 하는 형제 노드들이다.)
5. 뿌리 노드로부터 노드 q에 이르는 경로에 노드 p가 있으면 노드 p를 노드 조상 노드(ancestor)노드라고 한다. 노드 q는 노드 p의 자손(descendant)노드이다.
// A, B, F는 J의 조상 노드들이다.
6. 주어진 깊이의 모든 노드의 집합을 그 트리의 레벨이라고 한다.

7. 노드의 깊이는 뿌리로부터 그 노드까지의 경로의 길이이다.
  // F의 깊이는 2, A-C-G
8. 노드의 높이는 그 노드로부터 가장 깊은 노드까지의 경로의 길이이다. 트리의 높이는 뿌리로부터 가장 깊은 까지의 경로의 길이이다.
  // B의 높이는 2이다.(B-F-G)
9. 트리의 높이는 트리의 모든 노드의 높이 중 최대 값이고 트리의 깊이는 트리의 모든 노드의 깊이의 최대 값이다. 주어진 트리에 대해 높이와 깊이는 같은 값을 가진다. 하지만 각각의 노드에서의 값은 다를 수 있다.
10. 노드의 크기는 자기 자신을 포함하여 그 노드가 가진 자손의 수이다.
 // B의 크기는 4이다.
11. 트리의 모든 노드가 오직 한 개의 자식만을 가질 때(잎 노드를 제외하고) 이 트리를 경사(skew) 트리라고 한다. 모든 노드가 왼쪽 자식만을 가지면 왼쪽 경사 트리라고 한다.
반대의 경우에는 오른쪽 경사 트리라고 한다.

 - 이진 트리

각 노드가 자식이 없거나, 한 개 혹은 두 개의 자식을 가질 때 이진 트리라고 한다. 빈 트리 역시 유효한 이진 트리이다. 이진 트리는 뿌리와 왼쪽 부속 트리, 오른쪽 부속 트리라고 불리는 두 개의 분리된 이진 트리로 구성되어 있다고 볼 수 있다.

 - 이진 트리의 종류

엄격한 이진 트리: 모든 노드가 두 개의 자식을 가지거나 자식이 없을 때 엄격한 이진 트리

포화 이진 트리: 모든 노드가 두 개의 자식을 가지고 잎 노드가 같은 레벨에 있을 때 포화                     이진 트리
완전 이진 트리: 완전 이진 트리를 정의하기 전에, 이진 트리의 높이가 h라고 할 때, 완전
                  이진 트리에서는 뿌리부터 시작해서 각 노드에 번호를 매기면, 1부터 시작                   해서 트리 안의 노드 수까지의 완전한 순열을 얻는다. 탐색할 때 NULL                       포인터에게도 숫자를 매겨야 한다. 모든 잎 노드가 높이 h나 h - 1에 있고                   순열에서 빠진 숫자가 없을 때 완전 이진 트리라고 부른다.

 - 이진 트리 속성
1. 포화 이진 트리의 노드 개수 n은 2^(h+1) - 1이다. 모두 h 레벨이 있기 때문에 각 레벨의 노드를 다 더해야 한다.(2^0 + 2^1 + 2^2 + 2^3 + 2^4 +... + 2^h = 2^(h+1) - 1
2. 완전 이진 트리의 노드 개수 n은 2^h(최소 값)과 2^(h+1) - 1(최대 값) 사이에 있다.
3. 포화 이진 트리의 잎의 개수는 2h이다.
4. n개의 노드를 가진 완전 이진 트리의 NULL 연결(낭비된 포인터)의 개수는 n + 1이다.


 - 이진 트리의 구조
이제 이진 트리의 구조를 정의해보자. 예를 들어 노드의 데이터가 정수라고 하자. 다음 그림은 왼쪽과 오른쪽 자식을 가리키는 두 연결을 가진 데이터 필드로, (데이터를 포함한) 노드를 표현한 것이다.

class BinaryTreeNode {

    int data;

    class BinaryTreeNode *left;

    class BinaryTreeNode *right;

};

 - 이진 트리의 연산

   기본 연산

 트리에 항목 삽입하기

 트리로부터 항목 삭제하기

 항목 검색하기

 트리 탐색하기

   부가적 연산 

 트리의 크기 구하기
 트리의 높이 구하기
 최대의 합을 가진 레벨 찾기
 주어진 노드 쌍에 대해 최소 공통 조상 찾기
 ...  ...


 - 이진 트리 탐색
트리를 처리하기 위해서는 트리를 탐색하는 방법이 필요하다. 트리의 모든 노드를 방문하는 과정을 트리 탐색이라 한다. 각 노드는 오직 한 번씩 처리되지만 한 번 이상 방문될 수도 있다. 선형 데이터 구조(연결 리스트, 스택 , 큐)에서는 항목들이 순차적으로 방문된다.
그러나 트리 구조에서는 여러 가지 방법이 있다.
트리 탐색은 트리를 검색과 기본적인 동작이 같지만, 탐색의 목적은 특정한 순서로 트리 안을 움직이는 것이다. 또한 탐색에서는 모든 노드가 처리되지만 검색에서는 찾는 노드가 발견되면 멈L춘다.


 - 탐색 가능성
이진 트리의 뿌리부터 시작해서 모든 노드를 탐색하는 데는 세 가지 단계가 있는데, 이 단계들의 수행 순서에 따라 탐색 유형이 달라진다. 이 단계들은 현재 노드에 대해 어떤 작업 수행하기(노드를 '방문'한다고 하고 'D'라고 표기한다), 왼쪽 자식 노드 탐색하기('L'이라고 표기한다), 그리고 오른쪽 자식 노드 탐색하기('R'이라고 표기한다)이다. 이 과정은 재귀적 방법으로 쉽게 표현할 수 있는데, 다음과 같은 여섯 가지 가능성이 있다.
1. LDR: 왼쪽 부속 트리를 처리하고, 현재 노드의 데이터를 처리하고, 오른쪽 부속 트리를             처리한다.
2. LRD: 왼쪽 부속 트리를 처리하고, 오른쪽 부속 트리를 처리하고, 현재 노드의 데이터를            처리한다.
3. DLR
4. DRL
5. RDL
6. RDL


 - 탐색 분류하기
이 요소들이 처리되는 순서가 특정한 탐색 기법을 정의하게 된다. 현재 노드가 처리되는 순서에 따라 분류가 된다. 즉 현재 노드(D)에 의해 분류하는데, D가 가운데에 온다면 D의 왼쪽에 L이 오거나 상관없다. 비슷하게, D의 오른쪽에 L이 오거나 R이 오거나 상관없다. 이런 특성 때문에 모두 여섯 가지 가능성이 다음의 세 가지로 줄어든다.
1. 전위 탐색(DLR)
2. 중위 탐색(LDR)
3. 후위 탐색(LRD)

앞의 순서와 상관없는 또 다른 탐색 기법이 하나 더 있다.

레벨 순서 탐색: 이 기법은 너비 우선 탐색의 영향을 받은 것이다.

다음 그림을 기반으로 설명한다.

전위 탐색
전위 탐색에서 각 노드의 탐색은 부속 트리를 탐색하기 전에 처리된다. 각 노드가 부속 트리 전에 처리되더하도 몇몇 정보는 탐색이 트리의 다음 순서로 이동하는 동한 유지되어야 한다. 1이 먼저 처리되고 나서 왼쪽 부속 트리, 오른쪽 부속 트리 순서로 처리된다. 왼쪽 부속 트리 처리 후 오른쪽 부속 트리로 이동하려면 뿌리의 정보가 유지되어야 한다. 이런 정보를 위한 ADT는 당연히 스택인데, 스택의 LIFO 구조 때문에 오른쪽 부속 트리에 대한 정보를 역순으로 얻는 것이 가능하다.
  전위 탐색은 다음과 같이 정의된다.
1. 뿌리를 방문한다.
2. 전위 탐색으로 왼쪽 부속 트리를 탐색한다.
3. 전위 탐색으로 오른쪽 부속 트리를 탐색한다.

앞의 트리의 노드는 1 2 4 5 3 6 7의 순서로 방문된다.

void PreOrder(BinaryTreeNode root) {
  if(root != null) {
     System.out.println(root.getDate());
     PreOrder(root.getLeft());
     PreOrder(root.getRight());
    }
}

시간 복잡도: O(n)
공간 복잡도: O(n)

중위 탐색
중위 탐색에서는 뿌리 노드가 탐색에서는 뿌리 노드가 부속 트리 사이에 방문된다. 중위 탐색은 다음과 같이 정의된다.

1. 왼쪽 부속 트리를 중위 탐색으로 탐색한다.
2. 뿌리 노드를 방문한다.
3. 오른쪽 부속 트리를 중위 탐색으로 탐색한다.

앞의 트리 노드는 4 2 5 1 6 3 7의 순서로 방문된다.

void InOrder(BinaryTreeNode root) {
     if(root != null) {
        InOrder(root.getLeft());
       System.out.println(root.getData());
       InOrder(root.getRight);
    }
}

시간 복잡도: O(n)
공간 복잡도: O(n)

후위 탐색
후위 탐색에서 뿌리 노드는 양쪽 부속 트리 뒤에 방문된다. 후위 탐색은 다음과 같이 정의된다.

1. 왼쪽 부속 트리를 후위 탐색으로 탐색한다.
2. 오른쪽 부속 트리를 후위 탐색으로 탐색한다.
3. 뿌리 노드를 방문한다.

앞의 트리 노드들은 4 5 2 6 7 3 1의 순서로 방문된다.

void PostOrder(BinaryTreeNode root) {
    if(root) {
       PostOrder(root.getLeft());
       PostOrder(root.getRight());
       System.out.println(root.getData());
    }
}

시간 복잡도: O(n)
공간 복잡도: O(n)

레벨 순서 탐색
레벨 순서 탐색은 다음과 같이 정의된다.

1. 뿌리 노드를 방문한다.
2. 레벨 l을 방문하는 동안 레벨 ㅣ + 1의 모든 항목을 큐에 저장한다.
3. 다음 레벨로 가서 그 레벨의 모든 노드를 방문한다.
4. 이 과정을 모든 레벨이 끝날 때까지 방문된다.

앞의 트리의 노드들은 1 2 3 4 5 6 7의 순서로 방문된다.

void LevelOrder(BinaryTreeNode root) {
   BinaryTreeNode temp;
   LLQueue Q = new LLQueue();
   if(!root)
       return;
   Q.enQueue(root);
   while(!Q.isEmpty()) {
       temp = Q.deQueue();
       // 현재 노드를 처리한다.
       System.out.println(temp.getData());
       if(temp.getLeft())
            Q.enQueue(temp.getLeft());
       if(temp.getRight())
            Q.enQueue(temp.getRight());
       }
   Q.deleteQueue();
}

시간 복잡도: O(n)
공간 복잡도: O(n)

데이터 구조와 알고리즘 5장

큐란 무엇인가?
큐(Queue)는 (연결 리스트와 스택과 유사하게) 데이터를 저장하는 데이터 구조이다. 큐에서는 데이터가 도착하는 순서가 중요하다. 일반적으로 큐는 사람들이나 물건들이 한 줄로 서서 차례를 기다리는 것과 비슷하다.

정의: 큐는 데이터의 삽입이 한쪽 끝(뒤, rear)에서 이루어지고 삭제는 다른 쪽 끝(앞, front)에서 이루어지는 정렬된 리스트이다. 가장 처음 삽입된 항목이 맨 먼저 삭제된다(FIFO)

스택에서처럼 큐는 두 가지 동작의 종류가 있다. 항목이 큐에 삽입될 때, 인큐(EnQueue)라고 하고, 항목이 큐로부터 제거될 때, 디큐(DeQueue)라고 한다. 빈 큐로부터 디큐하려고 하는 것을 언더플로우(underflow)라고 부르고, 꽉 찬 큐에 항목을 인큐하려고 하는 것을 오버플로우(overflow)라고 하는데, 일반적으로 예외로 처리된다.

 - 큐는 어떻게 사용되는가?

큐는 데이터의 순서를 유지해야 할 필요가 있는 경우에 매우 유용하다.

 - 큐 ADT

큐의 주된 연산들

EnQueue(int data): 큐의 가장 끝에 항목을 삽입한다.

int DeQueue(): 큐의 가장 앞의 항목을 제거하고 리턴한다.

큐의 보조 연산들

int Front(): 큐의 가장 앞에 있는 항목을 제거하지 않고 리턴한다.

int QueueSize(): 저장된 항목의 개수를 리턴한다.

int IsEmptyQueue(): 저장된 항목이 없는지를 나타낸다.

 - 예외들

다른 ADT들과 유사하게 빈 큐에 대하여 디큐하려고 시도하면 '빈 큐 예외(Empty Queue Exception)'가 발생하고, 꽉 찬 큐에 인큐하려고 하면 '꽉찬 큐 예외(Full Queue Exception)' 가 발생한다.

 - 큐의 구현

간단한 원형 배열에 기초한 구현

동적 원형 배열에 기초한 구현

연결 리스트 구현

왜 원형 배열인가?

먼저, 스택에서 사용했던 것처럼 단순한 배열을 사용할 수 있는지 살펴보자. 큐의 삽입은 한쪽 끝에서, 삭제는 다른 쪽 끝에서 이루어진다는 것을 알고 있다. 그런데 몇 번의 삽입과 삭제 연산 뒤에 다음 그림과 같은 상황에 처하는 경우가 많다.

 (배열의 앞쪽 공간이 낭비되는 현상)

이 문제는 원형 배열로 해결할 수 있는데, 원형 배열은 마지막 항목과 첫 번째 항목이 연결되는 형태이다. 이를 이용하여 앞쪽에 빈 공간이 있으면 뒤(rear)포인터가 다음 빈 공간으로 쉽게 이동할 수 있다.

간단한 원형 배열 구현

public class ArrayQueue {

     private int front;

     private int rear;

     private int capacity;

     private [] array;

     private ArrayQueue(int size) {

          capacity = size;

          front = -1;

          rear = -1;

          array = new int [size];

    }

    public static ArrayQueue createQueue(int size) {

        return new ArrayQueue(size);

    }

    public boolean isEmpty() {

        return (front == -1);

    }

    public boolean isFull() {

       return ((rear + 1) % capacity == front);

    }

    public int getQueueSize() {

       return ((capacity - front + rear + 1)%capacity);

    }

    public void enQueue(int data) {

        if(isFull()) {

              throw new QueueOverflowException("Queue Overflow");

        }else{

            rear = (rear + 1) % capacity;

            array[rear] = data;

            if(front == -1) {

                 front = rear;

            }

         }

      }

    public int deQueue() {

         int data = null;

         if(isEmpty()) {

                throw new EmptyQueueException("Queue Empty");

         }else{

              data = array[front];

             if(front == rear) {

                 front =rear - 1;

              }else{

                  front = (front+1)%capacity;

             }

         } 

        return data;

    }

}

 - 성능과 한계

동적 원형 배열 구현

public class DynArrayQueue extends Queue {

    private int front;

    private int rear;

    private int capacity;

    private int[] array;

    private DynarrayQueue() {

        capacity = 1;

        front = -1;

        rear = -1;

        array =new int[1];

    }

   public static DynArrayQueue createDynArrayQueue() {

       return new DynArrayQueue();

   }

   public boolean isEmpty() {

       return (front == -1);

   }

   private boolean isFull() {

       return ((rear + 1) % capacity == front);

   }

   public int getQueueSize() {

        if(front == -1) return 0;

        int size = (capacity - front + rear + 1) % capacity;

        if(size == 0) {

              return  capacity;

         }else return size;

   }

   private void resizeQueue() {

       int initCapacity = capacity;

       capacity *= 2;

       int[] oldArray = array;

       array = new int[this.capacity];

       for(int i=0; i<oldArray.length;i++) {

           array[i] = oldArray[i];

       }

       if(rear < front) {

           for(int i=0; i<front; i++) {

               array[i+initCapacity] = this.array[i];

               array[i] = null;

            }

            rear = rear + initCapacity;

       }

    }
   public void enQueue(int data) {

       if(isFull()) resizeQueue();

       rear = (rear + 1) % capacity;

       array[rear] = data;

       if(front == -1) front = rear;

   }

   public int deQueue() {

       int data = null;

       if(isEmpty()) throw new EmptyQueueException("Queue Empty");

       else { data = array[front];

             if(front == rear) front = rear = -1;

             else front = (front + 1) % capacity;

       }

       return data;

    }

 }

성능

연결 리스트 구현

public class LLQueue extends Queue {

     private LLNode frontNode;

     private LLNode rearNode;

     private LLQueue() {

          this.frontNode = null;

          this.rearNode = null;

     }

     public static LLQueue createQueue(){

         return new LLQueue();

     }

     public boolean isEmpty() {

         return (frontNode == null);

     }

     public void enQueue(int data) {

         LLNode newNode = new LLNode(data);

         if(rearNode != null) {

             rearNode.setNext(newNode);

         }

         rearNode = newNode;

         if(frontNode == null) {

             frontNode = rearNode;

         }

     }

     public int deQueue() {

          int data = null;

          if(isEmpty()) {

               throw new EmptyQueueException("Queue Empty");

          }else{

              data = frontNode.getData();

              frontNode = frontNode.getNext();

          }

          return data;

      }

 }

성능

데이터 구조와 알고리즘 4장

스택은 데이터를 저장하기 위해 사용되는 (연결 리스트와 유사한) 간단한 데이터 구조이다.
스택에서는 데이터가 도착하는 순서가 중요하다.

정의: 스택은 삽입과 삭제가 한쪽 끝에서 이루어지는, 순서가 매겨진 리스트이다. 이 끝을 탑이라고 부른다. 제일 마지막에 추가된 항목이 제일 먼저 삭제된다(LIFO, FILO).

스택이 가질 수 있는 두 가지 변화에 대한 특별한 이름이 있다. 스택에 항목이 삽입될 때, 이 것을 푸시(push)라고 부르고, 항목이 스택으로부터 삭제되는 것을 팝(pop)이라고 부른다. 빈 스택으로부터 항목을 팝하려는 것을 언더플로우(underflow)라고 하고, 가득 찬 스택에 푸시하려는 것을 오버플로우(overflow)라고 하는데, 일반적으로 이런 경우는 예외처리한다.

 - 스택 ADT

스택의 주요 연산들

push(int data): 데이터를 스택에 넣는다.

int Pop(): 스택에 제일 마지막에 추가된 항목을 스택으로부터 삭제하고 리턴한다.

스택의 보조적 연산들

int Top(): 스택에 마지막에 추가된 항목을 삭제하지 않고 리턴한다.

int Size(): 스택에 저장된 항목의 개수를 리턴한다.

int IsEmptyStack(): 스택에 항목이 저장되어 있는지 아닌지를 확인한다.

int IsFullStack(): 스택이 가득 찼는지 아닌지를 확인한다.

 - 스택의 구현

여러 가지 방법들

간단한 배열에 기반한 구현

동적 배열에 기반한 구현

연결 리스트 구현

간단한 배열 구현

이렇게 ADT를 구현할 때는 하나의 배열이 사용된다. 배열에 항목을 왼쪽에서 오른쪽으로 추가하면서 변수 하나를 사용하여 탑 항목의 인덱스를 추적한다.

스택 항목을 저장하는 배열은 가득 찰 수도 있다. 이 경우, 푸시 연산은 '꽉찬 스택 예외'를 발생시킨다. 유사하게 빈 스택으로부터 항목을 삭제하려고 하면 '빈 스택 예외'를 발생시킨다.

public class ArrayStack{

    private int top;

    private int capacity;

    private int[] array;

   public ArrayStack() {

      capacity = 1;

      array = new int[capacity];

      top = -1;

}

public boolean isEmpty(){

     /* 이 조건이 참이면 1이 리턴하고 아니면 0이 리턴된다. */

    return (top == -1);

}

public int isStackFull(){

    // 이 조건이 참이면 1이 리턴되고 아니면 0이 리턴된다.

    return (top == capacity - 1); //혹은 return (top == array.length);

}

public void push(int data) {

     if(isStackFull()) System.out.println("Stack Overflow");

     else // 'top'을 증가시키고 데이터를 'top'위치에 저장한다.

      array[++top] = data;

}

public int pop(){

    if(isEmpty()) { // top == -1은 스택이 비었음을 뜻한다

       System.out.println("Stack is Empty");

       return 0;

   }

  else return (array[top--]);

}

public void deleteStack(){

    top = -1;

}

}

성능과 한계

성능

스택 안의 항목의 개수를 n이라고 하자. 이 구현의 스택 연산 복잡도는 다음과 같다.

 - 동적 배열 구현

top이라는 인덱스 변수를 써서 스택에 가장 최근에 추가된 항목의 인덱스를 가리키게 했다.

항목을 추가하려면 top인덱스를 증가시키고 새 항목을 그 인덱스 자리에 넣는다. 유사하게 항목을 삭제하려면, top 인덱스의 항목을 취하고 top 인덱스를 감소시킨다. 우리는 top의 값을 -1로 두어 빈 스택을 나타낸다. 여전히 해결해야 할 문제는 고정된 크기의 배열 스택의 모든 항목이 다 찼을 때 처리하는 방법이다.

첫번째 시도

스택이 가득 찰 때마다 배열의 크기를 1씩 증가시키자.

문제점)

이 방식으로 배열 크기를 증가시키는 것은 비용이 너무 크다. 예를 들어 n = 1일 때 새 항목을 푸시하려면 크기가 2인 배열을 만들고 이전 배열의 모든 항목을 새 배열로 복사한 후 맨뒤에 새 항목을 추가해야한다. 또다른 경우로서 n = n-1일 때 새 항목을 푸시하려면, 크기가 n인 새 배열을 만들어 이전 배열의 모든 항목을 새 배열로 복사한 후 맨 뒤에 새 항목을 추가해야 한다. n번의 푸시 이후에 전체 시간 T(n0 (복사 연산의 횟수)은 1 + 2 + ... + n ≒ O(n^2)에 비례한다.

다른 접근 방법: 반복적인 두 배 확장

배열이 가득 차면, 크기가 2배인 새 배열을 만들어 항목들을 복사한다. 이 방법에서는 n개의 항목을 푸시할 때 n(n^2이 아닌)에 비례하는 시간이 걸린다. 처음에 n = 1에서 시작해서, n = 32일 때까지 계속한다고 하자. 즉 1,2,4,8,16일 때 두 배로 만든다는 것이다. 이를 분석하는 다른 방법은, n = 1일 때 새 항목을 추가하려면 현재 배열의 크기를 두 배로 만들고 모든 항목을 이전 배열에서 새 배열로 복사하는 것이다.

n = 1일때 한 번의 복사를 하고, n = 2일 때 두 번의 복사를 하고, n = 4일 때 네 번의 복사를 하는 식이다. n = 32가 될 때면 복사 연산의 총합은 1 + 2 + 4 + 8 + 16 = 31이고, 이것은 대략 2n(32)와 비슷하다. 자세히 관찰하면, 두 배로 만드는 연산을 logn번 하는 것을 알 수 있다. 이제 n번의 푸시 연산에 배열 크기를 두 배로 만드는 것을 logn번 수행하면, logn 항을 갖는다. n번의 푸시 연산의 전체 시간 T(n)은 연산의 횟수에 비례한다.

1 + 2 + 4 + 8 ... + n/4 + n/2 +n = 2n = O(n)

T(n)은 O(n)이고 푸시 연산의 상각 시간은 O(1)이다.

public class DynArrayStack {

   private int top;

   private int capacity;

   private int[] array;

   public DynArrayStack() {

       capacity =1;

       array = new int[capacity];

       top = -1;

}

public boolean isEmpty(){

  return (top == -1);

}

public int isStackFull(){

   return (top == capacity - 1);

}

public void push(int data) {

    if(isStackFull()) 

        doubleStack();

    array[++top] = data;

}

private void doubleStack(){

    int newArray[] = new int[capacity*2];

    System.arraycopy(array, 0 ,newArray, 0, capacity);

    capacity = capacity*2;

    array = newArray;

}

public int pop() {

    if(isEmpty()) System.out.println("Stack Overflow");

    else return (array[top--]);

}

public void deleteStack() {

     top = -1;

}

}

 - 성능

연결 리스트 구현

스택을 구현하는 또 다른 방법은 연결 리스트를 사용하는 것이다. 푸시 연산은 리스트의 맨 앞에 항목을 삽입하는 것으로 구현된다. 팝 연산은 리스트 가장 처음 노드를 삭제하는 것으로 구현된다.

public class LLStack extends Stack {

    private LLNode headNode;

    public LLStack() {

        this.headNode = new LLNode(null);

}

public void Push(int data){

    if(headNode == null) {

        headNode = new LLNode(data);

}else if(headNode.getData() == null){

     headNode.setData(data);

}else{

    LLNode llNode = new LLNode(data);

    llNode.setNext(headNode);

    headNode = llNode;

}

}

public int top() {

     if(headNode == null) return null;

     else return headNode.getData();

}

public int pop(){

     if(headNode == null) {

          throw new EmptyStackException("Stack empty");

}else{

     int data = headNode.getData();

     headNode = headNode.getNext();

     return data;

}

}

public boolean isEmpty() {

     if(headNode == null) return true;

     else return false;

}

public void deleteStack(){

     headNode = null;

}

}

 - 성능

 - 각 구현 방법의 비교

점진적 증가 기법과 두 배 확장 기법의 비교

점진적 증가 기법

푸시 연산의 상각 시간은 O(n)이다.

두 배 확장 기법

푸시 연산의 상각 시간이 O(1)이다.

 - 배열 구현과 연결 리스트 구현의 비교

배열 구현

연산의 수행에는 일정한 시간이 걸린다.

가끔 비용이 큰 두 배 확장 연산을 수행한다.

(빈 스택으로부터 시작하는) n번의 연산에 상각하는 n에 비례하는 시간이 걸린다.

연결 리스트 구현

부드럽게 커지고 작아진다.

모든 연산에 일정한 시간 O(1)이 걸린다.

모든 연산에 레퍼런스를 다루기 위한 부가적인 공간과 시간이 필요하다.

데이터 구조와 알고리즘 3장

연결 리스트

 - 연결리스트란?
데이터의 집합을 저장하기 위해 사용되는 데이터 구조인데, 다음과 같은 속성을 갖는다.
 연속되는 항목들이 포인터로 연결된다.
 마지막 항목은 NULL로 포인트한다.
 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다,
 (메모리가 허락하는 한) 필요한 만큼 길어질 수 있다.
 메모리 공간을 낭비하지 않는다(포인터를 위한 추가의 메모리를 필요로 한다).

 - 연결 리스트 ADT

연결 리스트의 주요 연산들
 삽입: 항목을 리스트에 추가한다.
 삭제: 지정된 위치의 항목을 리스트로부터 삭제하며 리턴한다.

연결 리스트의 보조적 연산들
 리스트 삭제: 리스트의 모든 항목을 삭제한다.(리스트도 삭제).
 개수 세기: 리스트의 항목의 개수를 리턴한다.
 리스트의 끝으로부터 n번째 항목 찾기


- 연결리스트와 배열 비교

배열 개요
배열의 항목을 저장하기 위해 메모리 블록 하나가 할당된다. 배열의 항목은 특정 항목의 인덱스를 첨자로 사용하여 일정한 시간으로 접근할 수 있다.
why?
처음에 데이터형에 따른 항목의 크기(int: 4바이트, float: 8바이트)가 계산되고, 그것이 항목의 인덱스에 곱해져서 기본 주소에 더해질 값이 된다.
이 두 연산이 일정한 시간이 걸므로 배열 접근은 일정한 시간으로 수행된다고 할 수 있다.

 - 배열의 장점
간단하고 사용하기 쉽다.
항목에의 접근이 더 빠르다.

 - 배열의 단점
고정된 크기: 배열의 크기는 정적이다.
한 블록의 할당: 처음에 배열을 할당할 때 전체 배열을 위한 메모리를 얻지 못할 때도 있다.
                  (배열의 크기가 클 경우)
복잡한 위치 기반의 삽입: 주어진 위치에 항목을 삽입하려면 기존의 항목들을 이동해야 할
수 있다. 이렇게 해야 원하는 위치에 새 항목을 추가할 자리가 생긴다. 만약 새 항목을 추가할 자리가 가장 앞이면 다른 항목들의 이동 연산이 더욱 오래 걸리게 된다.


 - 동적 배열
동적 배열은 랜덤 접근하는, 크기가 변하는 리스트 데이터 구조로 새로운 항목들이 추가되거나 삭제될 수 있다. 동적 배열을 구현하는 한 가지 간단한 방법은 처음에 고정된 크기의 배열로 시작하는 것이다. 이 배열이 가득 차면, 원래 배열의 두 배 크기의 새 배열을 만든다. 마찬가지로 배열의 항목의 수가 절반 이하가 되면 배열 크기를 반으로 줄인다.


- 연결 리스트의 장점
일정한 시간으로 확장 가능하다는 것이다. 배열을 만들기 위해서는 특정한 숫자의 항목을 위해 메모리를 할당해야만 한다. 배열에 항목을 추가하기 위해서는 새 배열을 만들어 원래 배열에서 새 배열로 항목들을 복사해야 한다. 그러나 이 방법은 시간이 오래 걸린다.
 이것을 막기 위해 처음에 많은 공간을 할당할 수도 있다. 하지만 이렇게 하면 필요한 것보다 더 많이 할당하게 되어 메모리를 낭비하게 된다. 이 때 연결 리스트를 사용하면 하나의 항목을 위한 공간으로 시작해서 복사나 재할당 없이 새 항목을 쉽게 추가할 수 있다.

 - 연결 리스트의 단점

1. 개별 항목에 접근하는 접근 시간이 길다는 것
   배열은 랜덤 접근이 가능하므로 배열의 항목에 접근하는 데 O(1)의 시간이 걸리다. 연결    리스트는 리스트의 항목에 접근하는 데 최악의 경우 O(n)의 시간이 걸린다.

2. 연결리스트를 변경하기 까다로운 경우
   마지막 항목이 삭제되면, 가장 끝에서 하나 전의 항목의 포인터가 NULL을 가리키도록      변경되어야만 한다.

3. 추가적인 참조 포인터를 위한 메모리 공간이 낭비된다.

연결리스트 배열 동적배열 비교

--단일 연결 리스트

public class ListNode {

   private int data;

   private ListNode next;

   public ListNode(int data){

      this.data = data;

}

   public void setData(int data){

       this.data = data;

}

   public int getData(){

      return data;

}

   public void setNext(ListNode next){

       this.next = next;

}

   public ListNode getNext(){

        return this.next;

}

}

 - 리스트의 기본 연산

 리스트 탐색하기

 리스트에 항목 삽입하기

 리스트에서 항목 삭제하기

 - 리스트 탐색하기

 '머리' 노드 포인터가 리스트의 첫 번째 노드를 가리킨다고 가정하자. 리스트를 탐색하기 위해 다음을 수행한다.

 1. 포인터를 따라간다.

 2. 탐색하면서 노드의 값을 표시한다

 3. '다음' 포인터가 NULL을 가리키면 멈춘다.

int ListLength(ListNode headNode) {

    int length = 0;

    ListNode currentNode = headNode;

    while(currentNode != null) {

       length++;

       currentNode = currentNode.getNext();

    }

    return length;

}

시간 복잡도: 크기가 n인 전체 리스트를 스캔하는 데 O(n)

공간 복잡도: 하나의 임시 변수를 만드는 데 O(1)

 - 단일 연결 리스트의 삽입

단일 연결 리스트에 삽입하는 경우는 세 가지가 있다.

1. 새 노드를 '머리' 노드 포인터 앞에 삽입하기
   새 노드의 '다음' 포인터를 현재의 '머리'를 가리키도록 업데이트
   '머리' 노드 포인터가 새 노드를 가리키도록 업데이트

2. 새 노드를 '꼬리' 노드 포인터 뒤에 삽입하기
   새 노드의 '다음' 포인터는 NULL을 가리킨다.
   마지막 노드의 '다음' 포인터는 새 노드를 가리킨다.

3. 새 노드를 리스트의 중간에 삽입하기.
    위치 노드의 '다음' 포인터가 새 노드를 가리키게 한다.
    새 노드의 '다음' 포인터가 위치 노드의 다음 노드를 가리키게 한다.

ListNode InsertInLinkedList (ListNode headNode, ListNode nodeToInsert, int position) {
       if(headNode == null)
           return nodeToInsert;
       int size = ListLength(headNode);
       if(position > size + 1 || position < 1) {
           System.out.println("Position of node to insert is invalid. The valid inputs are                                     1 to " + (size+1));
             return headNode;
           }
        if(position == 1){
             nodeToInsert.setNext(headNode);
             return nodeToInsert;
         }else{
            ListNode previousNode = headNode;
            int count = 1;
            while(count < position-1){
                 previousNode = previousNode.getNext();
                  count++;
             }
            ListNode currentNode = previousNode.getNext();
            nodeToInsert.setNext(currentNode);
           previousNode.setNext(nodeToInsert);
        }
        return headNode;
     }

시간 복잡도: 최악의 경우에 노드를 리스트의 가장 끝에 추가 해야 하므로 O(n)
공간 복잡도: 한 개의 임시 변수만을 생성하므로 O(1)


 - 단일 연결 리스트의 노드 삭제

1. 첫 번째 노드 삭제하기  
   임시 노드를 만들어 '머리' 포인터와 같은 노드를 가리키게 한다.
   '머리' 노드 포인터를 다음 노드로 옮기고 임시 노드를 삭제한다.

2. 마지막 노드 삭제하기
   리스트를 탐색하면서 마지막 하나 전 노드의 주소도 저장한다. 리스트의 가장 끝에 도달    했을 때 마지막 노드를 가리키는 포인터와 마지막 하나 전 노드를 가리키는 포인터, 두      개의 포인터를 갖고 있게 된다.
   마지막 노드 하나 전 노드의 '다음' 포인터를 NULL을 가리키도록 업데이트한다.
   마지막 노드를 제거한다.

3. 중간 노드 삭제하기
   리스트를 탐색하면서 삭제 할 노드 하나 전의 노드도 저장한다. 삭제할 노드를 찾았을 때    하나 전 노드의 '다음' 포인터를 삭제할 노드의 '다음' 포인터의 값으로 바꾼다.
   삭제할 현재 노드를 제거한다.

ListNode DeleteNodeFromLinkedList(ListNode headNode, int position) {
   int size = getLinkedListLength(headNode);
   if(position > size || position < 1) {
     System.out.println("Position of node to delete is invalid. The valid inputs are 1                                 to" + size);
       return headNode;
   }
    if(position == 1) {
    ListNode currentNode = headNode.getNext();
    headNode = null;
    return currentNode;
 } else {
    ListNode previousNode = headNode;
    int count = 1;
    while(count < position - 1) {
          previousNode = previousNode.getNext();
          count++;
     }
    ListNode currentNode = previousNode.getNext();
    previousNode.setNext(currentNode.getNext());
    currentNode = null;
  }
  return headNode;
}

시간 복잡도: O(n). 최악의 경우에 리스트 맨 마지막의 노드를 삭제해야 할 수도 있다.
공간 복잡도: O(1). 하나의 임시 변수만 생성하기 때문이다.

 - 단일 연결 리스트 삭제하기
 현재 노드의 값을 임시 변수에 저장하고 현재 노드의 메모리 할당을 해제하면 된다.
 현재 노드의 메모리 할당을 해제한 뒤에 임시 변수의 값을 이용해 다음 노드로 이동한 뒤    전체 노드에서 이 과정을 반복한다.

void DeleteLinkedList(ListNode head) {
    ListNode auxilaryNode, iterator = head;
    while(iterator != null) {
          auxilarayNode = iterator.getNext();
          iterator = null;
          iterator = auxilaryNode;
    }
}


-- 이중 연결 리스트

 - 장점: 리스트의 특정 노드로부터 양방향으로 탐색할 수 있다.
          //거꾸로 탐색 가능
 - 단점: 각 노드가 포인터를 하나 씩 더 필요로 하기 때문에 저장 공간이 더 필요하다.
          삽입, 삭제 연산이 조금 더 오래 걸린다.

 public class DLLNode{
      private int data;
      private DLLNode next;
      private DLLNode previous;
      public DLLNode(int data){
           this.data = data;
     }
     public void setData(int data){
         this.data = data;
     }
     public int getData(){
          return data;
     }
     public void setNext(DLLNode next){
        this.next = next;
     }
     public DLLNode getNext() {
        return this.next;
     }
     public void setPrevious(DLLNode previos) {
          this.previous = previous;
     }
     public DLLNode getPrevious(){
           return this.previous;
     }
 }


 - 이중 연결 리스트의 삽입

 1. 새 노드를 '머리' 노드 포인터 앞에 삽입하기
    새 노드의 '다음' 포인터가 현재의 '머리' 노드를 가리키도록 아래 그림의 점선을 업데이     트하고 새 노드의 '이전' 포인터는 NULL을 가리키게 한다.
    '머리' 노드의 '이전' 포인터가 새 노드를 가리키게 하고 새 노드를 '머리' 노드가 되게 한     다.

 2. 이중 연결 리스트의 가장 끝에 노드 삽입하기
     새 노드의 '다음' 포인터가 NULL을 가리키게 하고 '이전' 포인터가 리스트의 맨 마지막      노드를 가리키게 한다.
     리스트 맨 마지막 노드의 '다음' 포인터가 새 노드를 가리키게 한다.

 3. 이중 연결 리스트의 중간에 노드 삽입하기
     새 노드의 '다음' 포인터가 우리가 새 노드를 삽입하려고 하는 '위치' 노드의 다음 노드      를 가리키게 한다. 또한 새 노드의 '이전' 포인터가 '위치' 노드를 가리키게 한다.
     '위치' 노드의 '다음' 포인터가 새 노드를 가리키게 하고 '위치'노드 다음 노드의 '이전'      포인터도 새 노드를 가리키게 한다.

  DLLNode DLLInsert(DLLNode headNode, DLLNode nodeToInsert, int position) {
      if(headNode == null)   // 시작 부분에 삽입한다.
         return nodeToInsert;
      int size = getDLLLength(headNode);
      if(position > size + 1 || position < 1) {
         System.out.println("Position of nodeToInsert is invalid. " +
                               "The valid inputs are 1 to " + (size + 1));
         return headNode;
      }
      if(position == 1) {   //머리 부분에 노드를 삽입한다.
          nodeToInsert.setNext(headNode);
          headNode.setPrevious(nodeToInsert);
          return nodeToInsert;
     } else {   //끝이 될 때까지 중간에 노드를 삽입한다.
           DLLNode previousNode = headNode;
           int count = 1;
           while(count < position -1) {
               previousNode = previousNode.getNext();
               count++;
            }
            DLLNode currentNode = previousNode.getNext();
            nodeToInsert.setNext(currentNode);
            if(currentNode != null)
                currentNode.setPrevious(nodeToInsert);
            previousNode.setNext(nodeToInsert);
            nodeToInsert.setPrevious(previousNode);
        }
        return headNode;
  }

시간 복잡도:O(n). 최악의 경우에 리스트 가장 끝에 노드를 삽입해야 한다.
공간 복잡도:O(1). 하나의 임시 변수만 생성하기 때문이다.

 - 이중 연결 리스트의 노드 삭제

 1. 임시 노드를 만들어 '머리' 노드 포인터와 같은 노드를 가리키게 한다.
    이제, '머리' 노드 포인터를 다음 노드로 옮기고 '머리' 노드의 '이전' 포인터를 NULL을        가리키게 한다. 그런 다음 임시 노드를 삭제한다.

 2. 이중 연결 리스트의 마지막 노드 삭제하기
    리스트의 끝가지 탐색한다. 리스트의 끝에 도달했을 때는 마지막 노드의 '이전' 포인터       로 마지막 노드 하나 전 노드를 알 수 있다.
    마지막 노드 하나 전 노드의 '다음' 포인터를 NULL을 가리키게 한다.
    마지막 노드를 제거한다.

 3. 이중 연결 리스트에서 중간 노드 삭제하기
    리스트의 끝까지 탐색한다. 삭제할 노드를 찾으면 삭제할 노드 하나 전 노드의 '다음' 포     인터를 삭제할 노드 다음 노드를 가리키도록 한다. 그리고 삭제할 노드 다음 노드의 '이     전' 포인터를 삭제할 노드 하나 전 노드를 가리키도록 한다.
    현재 삭제할 노드를 제거한다.

  DLLNode DLLDelete(DLLNode headNode, int position) {
     int size = getDLLLength(headNode);
      //위치가 주어진 연결 리스트의 사이즈보다 클 경우 폐기한다.
     if(position > size || position < 1) {
       System.out.println("Position of node to delete is invalid.
               The valid inputs are 1 to " + size);
        return headNode;
      }
     if(position == 1) {   //시작 노드를 삭제
        DLLNode currentNode = headNode.getNext();
        headNode = null;
        currentNode.setPrevious(null);
       return currenNode;
     }else{   //끝이 될 때까지 내부의 노드를 삭제
        DLLNode previousNode = headNode;
        int count = 1;
        while(count < position-1) {
          previousNode = previousNode.getNext();
          count++;
        }
       DLLNode currentNode = previousNode.getNext();
       DLLNode laterNode = currentNode.getNext();
       previousNode.setNext(laterNode);
       if(laterNode != null)
          //마지막 노드가 NULL이 아닐 경우엔 이전 노드를 NULL로 설정
          laterNode.setPrevious(previousNode);
       currentNode = null;
   }
   return headNode;
 }

시간 복잡도: 크기 n인 리스트 전체를 탐색하므로 O(n)
공간 복잡도: 하나의 임시 변수만을 만들기 때문에 O(1)


-- 원형 연결 리스트

- 원형 연결 리스트의 노드 개수 세기
  노드의 개수를 세려면 '머리'라고 표시된 노드로부터 시작해서 '현재'라는 임시 노드를 하   나 사용하여 '현재' 노드가 시작점인 '머리'에 도달할 때까지 탐색한다.

int CircluarListLength(CLLNode headNode) {
    int length = 0;
    CLLNode currentNode = headNode;
    while(currentNode != null) {
       length++;
       currentNode =currentNode.getNext();
       if(currentNode == headNode)
          break;
     }
     return length;
 }

시간 복잡도: O(n), 크기 n인 전체 리스트를 탐색
공간 복잡도: O(1), 하나의 임시 변수만을 생성


 - 원형 연결 리스트의 내용 프린트하기
   값을 프린트하고 다음 노드로 이동하고 다시 프린트하기를 '머리' 노드에 다시 도달할 때    까지 계속 한다.

void PrintCircularListData(CLLNode headNode) {
   CLLNode CLLNode = headNode;
   while(CLLNode != null) {
        System.out.print(CLLNode.getData()+"->");
        CLLNode = CLLNode.getNext();
        if(CLLNode == headNode) break;
   }
   System.out.println("(" + CLLNode.getData() + ")headNode");
}

시간 복잡도: O(n), 크기 n인 전체 리스트를 탐색
공간 복잡도: O(1), 하나의 임시 변수만을 생성

 - 원형 연결 리스트의 가장 끝에 노드 삽입하기
    새 노드를 만들어 '다음 포인터를 일단 자기 자신을 가리키게 한다.
    새 노드의 '다음' 포인터가 '머리' 노드를 가리키게 한 다음, '꼬리' 노드까지 리스트를       탐색한다. 이 말은 원형 연결 리스트에서는 다음 노드가 '머리'노드에서 멈춰야 한다는       것이다.
    '머리'노드 이전 노드의 '다음 포인터가 새 노드를 가리키도록 업데이트를 하면 다음과       같은 리스트를 얻게 된다.

void InsertAtEndInCLL (LLNode headNode, LLNode nodeToInsert) {
     CLLNode currentNode = headNode;
     while(currentNode.getNext() != headNode) {
        currentNode.setNext(currentNode.getNext());
     }
     nodeToInsert.setNext(nodeToInsert);
      if(headNode == null) headNode = nodeToInsert;
     else{
          nodeToInsert.setNext(heaedNode);
          currentNode.setNext(nodeToInsert);
      }
   }

시간 복잡도: O(n), 크기 n인 전체 리스트를 탐색
공간 복잡도: O(1), 하나의 임시 변수만을 생성

 - 원형 연결 리스트의 가장 처음에 노드 삽입하기
    새 노드를 만들어 '다음' 포인터를 일단 자기 자신을 가리키게 한다.
    새 노드의 '다음' 포인터가 새 노드를 가리키도록 업데이트한다,
    새 노드를 '머리' 노드가 되게 한다.

void InsertAtBeginInCLL(LLNode headNode, LLNode nodeToInsert) {
     CLLNode currentNode = headNode;
     while(currentNode.getNext() != headNode) {
         currentNode.setNext(currentNode.getNext());
      }
     nodeToInsert.setNext(nodeToInsert);
     if(headNode == null)
         headNode = nodeToInsert;
     else {
          nodeToInsert.setNext(headNode);
          currentNode.setNext(nodeToInsert);
          headNode = nodeToInsert;
      }
 }

시간 복잡도: O(n), 크기 n인 전체 리스트를 탐색
공간 복잡도: O(1), 하나의 임시 변수만을 생성

- 원형 연결 리스트의 마지막 노드 삭제하기
  리스트를 탐색하며 마지막 노드와 그 전 노드를 찾는다.
  마지막 노드 하나 전 노드의 '다음' 포인터가 '머리'노드를 가리키게 한다.
  마지막 노드를 제거한다.

void DeleteLastNodeFromCLL(CLLNode head) {
   CLLNode temp = head;
   CLLNode currentNode = head;
   if(head == null) {
      System.out.println("List Empty");
      return;
    }
    while(currentNode.getNext() != headNode) {
       temp = currentNode;
       currentNode = currentNode.getNext();
    }
    currentNode = null;
    return;
 }

시간 복잡도: 크기 n인 전체 리스트를 탐색하므로 O(n)
공간 복잡도: 하나의 임시 변수만을 생성하므로 O(1)

 - 원형 연결 리스트의 첫 번째 노드 삭제하기
   리스트를 탐색하여 '꼬리' 노드를 찾는다. '꼬리'노드는 우리가 삭제할 '머리'노드의 하나    전 노드이다.
   '머리' 노드를 가리키는 임시 포인터를 만든다. 또한 '꼬리'노드의 '다음' 포인터가 '머리'    노드의 다음 노드를 가리키게 한다.
   이제, '머리' 포인터를 다음 노드로 옮긴다. 임시 포인터가 가리키는 노드를 제거한다.

 void DeleteFrontNodeFromCLL(CLLNode head) {
     CLLNode temp = head;
     CLLNode current = head;
     if(head == null) {
         Systen.out.println("List Empty");
         return;
     }
     while(current.getNext() != head)
           current.setNext(current.getNext());
     current.setNext(head.getNext());
     head = head.getNext();
     temp = null;
     return;
}

시간 복잡도: O(n), 크기 n인 전체 리스트를 탐색
공간 복잡도: O(1), 하나의 임시 변수만을 생성


 - 메모리-효율적인 이중 연결 리스트

일반적인 노드 정의
 class DLLNode {
     private int data;
     private DLLNode next;
     private DLLNode previous;
     ............
}

새로운 노드 정의
 public class ListNode {
     private int data;
     private ListNode ptrdiff;
     ............
}
ptrdiff 포인터는 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인터의 차이를 갖고 있다. 포인터 차이는 배타적 논리합(Exclusive OR, )연산을 사용해서 계산된다.

ptrdiff = 이전 노드를 가리키는 포인터  다음 노드를 가리키는 포인터

시작 노드('머리' 노드)의 ptrdiff는 NULL  다음 노드('머리' 노드의 다음 노드)이다.
이와 유사하게 마지막 노드의 ptrdiff는 이전 노드(마지막 노드의 이전 노드)  NULL이다.

어떻게 이것이 가능한가?

X  X = 0
X  0 = X
X  Y = Y  X (대칭성)
(X  Y)  Z = X  (Y  Z) (전이성)

앞의 예에서, 우리가 노드 C에 있는데 B로 이동하고 싶다고 가정하자. C의 ptrdiff는 B  D임을 알고 있다. B로 이동하고 싶다면, C의 ptrdiff와 D에 를 수행하면 된다.

(B  D)  D = B (D  D = 0이므로)
만약 D로 이동하고 싶다면, C의 ptrdiff와 B에 를 적용하면 D를 알 수 있다.

(B  D)  B = D (B  B = 0이므로)
앞의 논의에서 하나의 포인터만을 사용하여 리스트의 앞이나 뒤로 이동할 수 있다는 것을 알 수 있다. 이중 연결 리스트의 메모리-효율적인 구현은 시간 효율성을 아주 많이 잃지 않고도 실현 가능하다.