5. 연결 리스트

주요용어

1. 리스트 : ‘원소들 간의 순서’가 지켜지며 유지되는 자료구조
2. 리스트의 원소들 간의 순서 : 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 ‘논리적인 순서’, 혹은 리스트에 나타나는 원소들 간의 ‘의미적인 순서’
3. 리스트의 노드 : 원소값과 다음 원소를 가리키는 위치의 주소값으로 구성된 자료단위, 데이터 요소(원소)와 리스트의 다음 원소를 지시하는 포인터(pointer, 주소)를 가지는 자료단위
4. 포인터 : 메모리에 저장되는 값(데이터)의 저장 위치에 대한 주소를 가리키는 데이터형
5. 단항 연산자 : 피연산자를 하나만 갖는 연산자
6. 구조체(struct) : 다양한 데이터형의 변수를 하나의 상자 안에 넣어서 선언하거나 사용하는 C 프로그래밍 문법

---

리스트의 의미

• 일정한 순서의 나열
• 어떤 정의에 의해서 결정된 논리적인 순서의 나열
  (물리적인 순서는 상관 없음 / 배열의 경우는 논리적인 순서와 물리적인 순서가 동일해야 함 )
• 리스트의 순서는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는
  논리적인 순서 혹은 리스트에 나타나는 원소들 간의 의미적인 순서를 의미함
• 배열은 인덱스로 표현되는 순서가 배열 원소의 메모리 공간(주기억 장치, DDR)에서의 물리적인 위치를 의미함
• 하지만 리스트의 '순서' 개념은 어떤 정의에 의해서 결정된 논리적인 순서임
• 원소들의 물리적인 저장 순서나 위치와는 무관하게 원소들 간의 논리적인 순서만 유지함

리스트의 구현방법

• 포인터를 이용한 리스트의 구현방법
  : 원소값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 함께 구현하는 방법 (연결 리스트)
• 배열을 이용한 리스트의 구현 방법

배열을 이용한 리스트의 원소 삽입/삭제

• 배열의 확장
  : 초기 배열 선언에서 충분히 크게 하면 어느 정도는 배열의 추가 확장을 피할 수 있겠지만, 원소를 리스트의 중간에 삽입하기 위해서는 리스트의 원소값을 하나씩 뒤로 밀어야 하는 상황이 발생함
• '배열로 구현된 리스트'는 원소의 순서가 연속적인 물리적 주소에 저장됨
  • 원소를 삽입하거나 삭제하기 위해서는 해당 원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 앞으로 당겨야만 됨
  • 리스트 원소값의 이동은 원소수가 많을수록 프로그램의 수행시간을 증가시킴
• 배열을 이용한 리스트의 원소 삽입/삭제 시 발생하는 문제
  • 리스트의 원소 삽입은 프로그램의 실행 중에 메모리 할당을 필요로 하는 경우도 발생시킴
  • 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있음
  • 자료의 삽입 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발함

리스트 구현을 위한 포인터

• 노드의 구조
  • 노드(node): 리스트의 원소(값) + 다음 원소를 가리키는 정보
  • 노드는 데이터 요소(원소, 값)와 리스트의 다음 원소를 지시하는 포인터(주소, 링크(link))로 구성됨: 자료와 링크

구조체의 구현

• 리스트의 생성
  • 정수 값 data와 링크 link로 구성된 노드의 생성

  struct linked_list_node {
    int data;
    struct linked_list_node *link;
  }

  

 

포인터의 구현

• 포인터의 할당과 반환 예

int a, *p_a;
float b, *p_b;
p_b = (int *)malloc(sizeof(int));
p_b = (float *)malloc(sizeof(float));
*p_a = 10;
*p_b = 3.14;
printf("a is %d, b is %f₩n", *p_a, *p_b);
free(p_a);
free(p_b);

연결 리스트에서 노드의 삭제

• 리스트의 원소 삭제 연산 단계
  1. 삭제할 노드의 선행 노드의 링크 필드를 삭제할 노드의 후행 노드를 가리키게 한다.
  2. 삭제할 노드를 메모리에 반환한다.

연결 리스트에서 노드의 삽입

• 리스트의 원소 삽입 연산 단계
  1. 메모리 공간을 할당받고 삽입할 내용을 저장하여 삽입할 x 노드를 생성합니다.
  2. x 노드의 링크부분이 후행 노드가 될 j 노드를 가리키게 합니다.
  3. 삽입될 x노드의 선행 노드가 될 i 노드의 링크 필드가 x 노드를 가리키게 합니다.

연결 리스트의 마지막에 삽입연산(1-1)

void addNode(linkedList_h* H, int x){
  // 리스트 마지막 노드에 삽입 연산하며, x값은 100이라고 가정함
  listNode* NewNode;
  listNode* LastNode;
  NewNode = (listNode*)malloc(sizeof(listNode));
  NewNode -> data = x;
  NewNode -> link = NULL;
}

연결 리스트의 마지막에 삽입연산(1-2)

void addNode(linkedList_h* H, int x){
  if(H -> head == NULL){ // 현재 리스트가 공백인 경우
    H -> head = NewNode;
    return;
  }
  LastNode = H -> head;
  while(LastNode -> link! = NULL){
    LastNode = LastNode -> link;
    LastNode -> link = NewNode;
  }
}

---

정리하기

1. 리스트의 ‘순서’는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 ‘논리적인 순서’, 혹은 리스트에 나타나는 원소들 간의 ‘의미적인 순서’를 의미합니다.
2. 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있습니다. 자료의 삽입과 삭제가 빈번히 발생하는 상황에서, 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발합니다.
3. 포인터를 이용하는 방법은 원소의 자리에는 원소값을 저장하고, 다음 원소를 가리키는 정보의 자리에는 다음 원소가 저장될 위치의 주소값을 저장합니다. 조금 더 ‘프로그램’스럽게 설명하자면, 리스트의 원소의 자리와 다음 원소를 가리키는 정보의 자리를 합쳐서 노드(node)라고 합시다. 노드에는 데이터 요소(원소)와 리스트의 다음 원소를 지시하는 포인터(pointer, 주소)를 가진다고 생각하면 됩니다. 이 포인터는 링크(link)라고도 부릅니다.
4. 포인터의 ‘메모리 주소값’이라는 것은 메모리에 저장되는 값의 위치라고 생각하면 됩니다. 메모리에 저장되는 값(데이터)은 저장 위치에 대한 주소를 가지며, 이 저장 위치를 이용해서 리스트의 원소값을 찾아갈 수 있습니다.
5. 다양한 데이터형의 변수를 하나의 상자 안에 넣어서 선언하거나 사용하는 C 프로그래밍 문법이 구조체(struct)입니다.