데이터 구조와 알고리즘 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이므로)
앞의 논의에서 하나의 포인터만을 사용하여 리스트의 앞이나 뒤로 이동할 수 있다는 것을 알 수 있다. 이중 연결 리스트의 메모리-효율적인 구현은 시간 효율성을 아주 많이 잃지 않고도 실현 가능하다.