자료 구조 - 리스트

‘c++로 쉽게 풀어쓴 자료구조 1판 - 천인국, 최영규’ 책을 참고하여 작성한 포스트입니다.

리스트

리스트란?

리스트(list) 또는 선형 리스트(linear list)는 항목들 사이에 순서가 있는 선형 자료구조이다. 리스트의 특징은 임의의 위치에 있는 항목에 대한 연산을 허용하는 것이다.

연결 리스트와의 차이

• 리스트는 특정한 자료 구조를 말하며, 연결 리스트는 어떤 자료 구조를 구현하는 프로그래밍 기법이다.

리스트의 추상 자료형

데이터: 임의의 접근 방법을 제공하는 같은 타입 요소들의 순서 있는 모임  
연산
 - insert(pos, item): 리스트의 pos 위치에 새로운 요소 item을 삽입
 - delete(pop): 리스트의 pos 위치에 있는 요소를 삭제한다.
 - getEntry(pos): 리스트의 pos 위치에 있는 요소를 반환한다.
 - isEmpty(): 리스트가 비어 있는지를 검사한다.
 - isFull(): 리스트가 가득 차 있는지를 검사한다.
 - find(item): 리스트에 요소 item이 있는지를 검사한다.
 - replace(pos, item): 리스트의 pos 위치에 있는 요소를 새로운 요소 item으로 바꾼다.
 - size(): 리스트 안의 요소의 개수를 반환한다.
 - display(): 리스트 안의 모든 요소들을 출력한다. 

구현 방법

리스트도 스택이나 큐와 같이 배열을 사용할 수도 있고 포인터를 이용한 연결 리스트로 구현할 수도 있다. 배열을 이용하면 쉽게 구현이 가능하겠지만 리스트에 저장 가능한 요소의 개수에 제한이 생기며, 아주 큰 배열을 미리 선언한다면 메모리 낭비의 비효율을 감수해야 한다.
게다가 삽입과 삭제를 임의의 위치에서도 할 수 있기 때문에 많은 요소들을 이동해야 하는 문제가 생긴다. 그래서 실제 프로그램들에서 사용하는 리스트는 대부분 포인터를 사용한 연결 리스트 방식을 이용한다.
연결 리스트 방식은 단순 연결 리스트와 이중 연결 리스트 두 가지 방법으로 나뉜다.

배열로 구현한 리스트

리스트의 모든 요소들은 배열의 첫 번째 위치부터 차곡차곡 저장되어야 하고, 중간에 비어 있는 항목이 없어야 한다.

1. 삽입 연산
   • 이미 요소들이 저장되어 있는 상태에서 빈 공간이 아닌 곳에 새로운 요소를 삽입하는 연산을 하려면 먼저 해당 위치 뒤에 있는 모든 요소들을 한칸씩 뒤로 옮겨야 한다.

      /// idx 위치에 num을 삽입하는 경우
      // length : 리스트 내 원소의 개수 
      void insert(int idx, int num) {
     // 리스트가 가득 차 있지 않아야 하고,
     // 인덱스가 삽입 가능한 범위 내에 있어야 함
     if(length != MAX_LIST_SIZE && idx >= 0 && idx <= length) {
       // 삽입 위치 원소부터 뒤 원소들을 뒤로 한칸씩 옮김
       for(int i=idx; i<length; i++) {
         arrayList[i+1] = arrayList[i];
       }
       // 원소들을 옮겨 생긴 빈 공간에 원소 삽입
       arrayList[idx] = num; 
       length += 1; // 원소의 개수 증가
     } else {
       printErrorMSG("List is full");
     } 
      }
     

2. 삭제 연산
   • 삽입 연산과 반대이다.

      // idx 위치의 원소 삭제
      void remove(int idx) {
     // 원소가 없는 위치의 원소를 삭제하려는 경우
     if(length != 0 && length > idx && idx >= 0) {
       // 삭제 위치 뒤의 원소들을 한 칸씩 앞으로 옮김
       for(int i=idx; i<length; i++) {
         arrayList[i] = arrayListp[i+1];
       }
       length -= 1; // 원소의 개수 감소
     } else {
       printErrorMSG("no element at the idx in the list");
     }
      }
     

구현 (해보기)

나머지 연산 등을 합친 코드.. 구현 하기

연결 리스트로 구현된 리스트

• 리스트를 연결 리스트로 구현하면 배열의 경우와 달리 비효율적인 많은 자료의 이동을 하지 않아도 된다.
• 앞서서는 연결 리스트 사용 시 헤드 포인터를 사용 하였다. 여기서는 헤드 노드를 사용해 보겠다. 헤드 노드에서의 링크가 원래의 헤드 포인터 역할을 한다.
• 객체 지향적 관점에서, 노드 클래스에서 가능한 많은 기능을 구현하고, 리스트 클래스에서 이들을 사용함으로써 리스트 클래스의 복잡도를 줄이겠다.
• 예를 들어 어떤 노드에서 자신의 다음 노드를 삭제하거나, 자신 노드 다음에 어떤 노드를 삽입하는 등의 작업은 저체 리스트 정보가 없어도 가능하다. 이런 것들을 노드 클래스에 멤버 함수로 구현해주면 좋을 것이다.

구현 (해보기)

다양한 형태의 연결 리스트

원형 연결 리스트(circular linked list)

리스트의 마지막 노드의 링크가 NULL이 아닌 첫 번째 노드를 가리키는 연결 리스트를 말한다.

원형 연결 리스트의 장점으로는,

• 한 노드에서 다른 모든 노드로의 접근이 가능함
• 리스트의 끝에 노드를 삽입하는 연산이 효율적임
• 헤드 포인터를 리스트의 마지막 노드를 가리키게 하면 상수 시간안에 리스트의 끝에 노드 삽입, 삭제가 가능함

이중 연결 리스트(doubly linked list)

하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트이다.

• 링크가 양방향이므로 양방향으로 검색이 가능하다.
• 단점은 공간을 많이 차지하고 코드가 복잡해진다는 것이다.
• 삽입과 삭제 시 네 단계 처리가 필요하다..

  이중 연결 리스트로 구현된 리스트

  (구현해보기)

• 선행 또는 후속 노드가 있는 경우에만 삽입 삭제를 해야 한다는 점에 유의?

  이중 연결 리스트로 구현한 덱

  (구현해보기)
  (후단 연산도 상수 시간에 되게 해보기)