3. 리스트

본 카테고리에 게시되는 글은 제가 편입을 준비하며 정리한 자료들입니다.

참조한 서적은 다음과 같습니다.

1. C언어로 쉽게 풀어 쓴 자료구조. 천인국·공용해·하상호. 생능출판사

2. 윤성우의 열혈 자료구조. 윤성우. 오렌지미디어

학부 편입 면접을 위해 준비한 자료이기 때문에 지나치게 긴 코드 또는 너무 깊은 내용은 배제했습니다.

---

※ tip

배열, 리스트 => 물리적 구조

트리, 스택, 큐 => 논리적 구조

1. 리스트의 개념

(1) 리스트

ㆍ말 그대로 ‘목록’을 의미함. 데이터를 관리하기 쉽게 목록으로 형성해 추가 삭제 수정이 용이하도록 만든 자료구조.

ㆍ배열을 이용한 구현, 연결 리스트 구현이 있음 (but 일반적으로 리스트 == 연결리스트임)

(2) 배열 리스트 vs 연결 리스트

배열 리스트	연결 리스트
최대 크기 고정적 - 쓰지 않는 공간으로 인한 비효율 발생 - 삽입할 수 있는 항목의 개수가 제한적	크기 제한X(동적으로 크기 할당) - 낭비되는 메모리가 없음 - 삽입할 수 있는 항목의 개수 제한X
삽입 삭제시 요소 이동 발생 (삽입․삭제시 요소이동으로 인한 오버헤드↑)	삽입 삭제시 요소 이동 없음 (삽입․삭제시 링크만 관리해주면 됨. 오버헤드가 ↓)
인덱스를 이용한 즉각적인 접근 가능 (탐색속도 ↑)	인덱스가 없어서 탐색 과정이 필요함

 

2. 배열로 구현한 리스트

(1) 배열 리스트

ㆍ고정된 배열을 할당 후, 해당 배열 크기 내에서 리스트 구성

(2) 장단점

ㆍ 장점

ㆍ 탐색 속도가 빠르다 (인덱스를 통한 즉각적 접근 가능)

ㆍ연결 리스트에 비해 구현이 비교적 간단하다.

ㆍ 단점 

ㆍ고정된 크기를 사용한다.

ㆍ 배열 크기보다 많은 데이터가 들어올 경우 삽입이 불가능하다.

ㆍ 배열 크기보다 적은 데이터만 들어온 경우, 나머지 공간은 낭비된다.

ㆍ 삽입․삭제시 요소의 이동이 빈번하게 발생한다.

ㆍ A,B,D,E,F 가 순서대로 배열에 저장되어 있을 때, B다음 자리에 C를 삽입하려면 D,E,F를 한 칸씩 뒤로 이동시켜야 함.

   ex) A,B,C,D가 저장되어 있을 때, A를 삭제한 경우 B,C,D를 한 칸씩 앞으로 이동시켜야 함.

(3) 배열 리스트 구현

1) 리스트 구조체

ㆍ리스트로 쓸 list[]배열, 저장된 자료 개수를 나타내는 length를 필드로 가지는 구조체다.

 

2) init함수 ⇒ length = 0으로 초기화한다.

    is_empty함수 ⇒ length == 0이면 TRUE(1)반환, 아니면 FALSE(0)반환한다.

    is_full함수 ⇒ length == MAX_SIZE 이면 T, 아니면 F반환

    출력함수display ⇒ 변수 i를 선언해 i를 인덱스로,

                              for(i=0 ; i<L->length ; i++) L->list[i]; 문을 돌려서 순차적으로 배열의 요소들을 출력한다.

3) 삽입함수 add

ㆍ 배열이 꽉 찼는지 검사한다(is_full) && 삽입 위치가 적절한지 검사한다.

- 삽입 위치의 적절성 검사 : 삽입 위치<= length 인지 검사 + 삽입위치 >= 0인지 검사

   (0~length 자리에만 삽입가능)

            ex)

0	1	2	3	4
A	B	C

                                                            ↑           ↑                 ↑

                                                           length-1 length     length+1(삽입불가)

ㆍ 삽입위치 뒤에 있는 데이터들을 한 칸씩 뒤로 이동

          (주의!! 맨 뒤 데이터부터 한칸씩 이동해야 함! 안그러면 덮어쓰기돼서 지워짐!)

ㆍ 삽입

4) 삭제함수 delete

ㆍ 삭제 데이터를 저장해둘 item변수 사용

ㆍ 삭제 위치의 적절성 검사

ㆍ 데이터 삭제

ㆍ 삭제 위치에서 length-2까지, 데이터 한 칸씩 당김 (arr[i+1]을 arr[i]에 대입)

ㆍ length --;

 

3. 연결 리스트로 구현한 리스트

(1) 연결 리스트

ㆍ data와 link부분을 가지는 자기참조 구조체 노드를 생성 후, link로 각 노드를 연결하여 구성

ㆍ node생성시마다 메모리를 동적 할당(즉, node 개수는 계속 늘릴 수 있음)

ㆍ 데이터 삽입․삭제 시 요소 이동 없음. link만 바꿔주면 됨.

ㆍ 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트 등이 있음

(2) 장단점

ㆍ 장점 

ㆍ 공간을 융통성있게 활용할 수 있음

ㆍ데이터가 삽입될 경우 노드를 동적 할당받아 리스트를 확장하기 때문에 이론상 공간의 제약이 없음.

ㆍ필요한 경우에만 노드를 할당하기 때문에 공간의 낭비가 없음.

ㆍ 삽입․삭제시 실질적인 데이터의 이동이 없음. link만 수정하면 됨.

ㆍ 단점 

ㆍ 특정 노드에 접근하기 위해서는 link를 타고 포인터를 해당 노드까지 이동시켜야 함.

        (배열 인덱스처럼 특정 요소에 직접 접근할 수 있는 수단이 없음)

ㆍ link필드를 위한 공간이 추가적으로 할애됨.

ㆍ 배열에 비해 구현이 복잡함.

 

(3) 연결 리스트로 구현한 리스트의 구현

※ 단순/원형/이중 연결 리스트 중 어떤 것을 사용할 것인지, 헤드 노드를 사용할 것인지, tail포인터를 사용할 것인지 등등 다양한 선택지가 존재한다. 여기서는 제일 기본적인 단순 연결 리스트로 헤드 노드 없이(헤드 ‘노드’를 안쓴다는 말이지 당연히 헤드포인터는 있다.) 구현한다는 가정하에 설명함.

1) 노드 구조체

typedef int element;

typedef struct ListNode {

element data;

sttruct ListNode *link;

} ListNode;

2) 리스트 구조체

typedef struct {

ListNode *head; // 헤드 포인터

int length; // 노드 개수

} LinkedListType;

 (main 함수에서 리스트가 필요하면 언제든지 LinkedListType list1; 으로 리스트를 생성할 수 있다.)

3) is_empty

ㆍ 헤드가 NULL을 가리키면 TRUE(1), FALSE(0)을 반환한다.

4) get_length

ㆍlength필드를 반환한다.

5) 삽입연산 add

ㆍ 연결 리스트의 연산인 get_node_at으로 position-1(삽입위치의 선행위치) 위치의 주소값을 얻는다.

ㆍ 마찬가지로 연결 리스트의 연산인 insert_node로 노드를 삽입한다.

ㆍ 핵심 기능이 이미 연결 리스트 연산에 정의되어 있으므로, 사실상 add연산이 하는 일은 입력 위치가 적절한지 판단하고, 노드 할당하고,     NumOfData증가시키는 부수적인 일이다.

※ 시험장에서 문제풀 때를 대비해 add연산 복습할때는 get_node_at, insert_node도 같이 구현해보자.

1. 주어진 위치에 데이터를 삽입하는 add함수

void add(LinkedListType *list, int position, element data)

{

    ListNode *p;

    if ((position)>=0) && (position<=list->length)) // 삽입 위치의 적절성 판단

    {

         ListNode *node = (ListNode *)malloc(sizeof(ListNode)); // 메모리 동적 할당.

         if(node == NULL) error("메모리 할당 에러“);  // 동적할당 실패한 경우 에러 출력. 

         

         node->data = data // 생성한 노드에 데이터 삽입

         p = get_node_at(list, position-1); /* get_node_at함수로 삽입위치의 선행노드 위치를 받음.

                                      (이거 p를 삽입위치 선행노드 까지 보내는거랑 동일한 개념임) */

         insert_node(&(list->head), p, node) // insert_node함수를 이용해 노드 삽입

         list->length++; // 리스트의 총 데이터 개수 ++

      }

}

※ get_node_at 함수(4, 연결 리스트 파트 참조)

ListNode *get_node_at(LinkedListType *list, int pos) // pos위치의 노드를 찾아 해당 노드의 주소값을 반환한다.

{                                               ※ pos-1을 전달하면 선행노드 주소값 얻을 수 있음!

   int i;

   ListNode *p = list->head;  // 탐색을 위한 포인터 p생성 및 list->head위치를 가리키도록 초기화.

   if(pos<0) return NULL; // 찾을 위치를 음수로 주면 NULL을 반환한다.

   for(i=0; i<pos; i++)

      p = p->link;       // 포인터 p를 pos위치까지 link타고 옮긴다.

   return p;

}

※ insert_node 함수(4. 연결 리스트 파트 참조)

// phead : 리스트 헤드 포인터의 포인터. 함수 내부에서 헤드포인터가 가리키는 대상을 변경할 필요가 있으므로 이중 포인터로 받음.

// p : 선행 노드 위치(주소)

// new_node : 삽입될 노드. add함수에서 malloc되어 전달됨.

void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)

{

    if(*phead == NULL) {   // 공백 리스트인 경우

       new_node->link = *phead;

       *phead = new_node;

    }

    else if(p==NULL){      // 첫 번째 노드로 삽입하는 경우(p==NULL)

        new_node->link = *phead;

        *phead = new_node;

     }

     else {                 // p다음 위치에 삽입하는 경우(p!=NULL)

         new_node->link = p->link;

         p->link = new_node;

      }

}

Q) 구태여 **head이중 포인터로 쓸 필요 있나? 그냥 List구조체 주소값을 &list로 넘겨서 list->head해도 헤더포인터 변경할 수 있는거 아닌가?

A) 맞다. 그런데 지금은 연결리스트로 구현된 ‘리스트’를 하는게 아니라 연결리스트를 하는 중이다. 무슨 말이냐면 아직 연결리스트를 구현하는 단계지, 연결리스트로 리스트를 구현하는게 아니니까 ADT에 리스트 구조체라는게 포함되어 있지 않다. 그니까 ListNode구조체는 있는데, ListType구조체는 없다. 그건 ‘리스트’의 ADT에 포함되는 것이다.

2. 리스트의 끝에 데이터를 삽입하는 add_last함수

void add_last(LinkedListType *list, element data)

{

     add(list, get_length(list), data);

}

3. 리스트의 처음에 데이터를 삽입하는 add_first함수

void add_first(LinkedListType *list, element data)

{  add(list, 0, data); }