포인터와 연결 리스트: 동적 자료 구조의 핵심 이해하기

프로그래밍에서 포인터와 연결 리스트는 동적 메모리 할당과 데이터 구조 관리에 매우 중요한 역할을 합니다. 이번 포스팅에서는 포인터의 개념과 연결 리스트를 어떻게 활용하는지 알아보겠습니다.

 

1. 포인터란 무엇인가?

포인터는 변수의 메모리 주소를 저장하는 변수입니다. 포인터를 통해 프로그램에서 변수의 값을 간접적으로 변경하거나 메모리의 특정 위치에 접근할 수 있습니다.

 

포인터의 기본 문법:

int *p;  // 정수형 포인터 선언
p = &a;  // 변수 a의 주소를 p에 저장

 

포인터를 사용한 값 변경 예시:

int a = 10;
int *p = &a;
*p = 20;  // a의 값을 20으로 변경

 

포인터를 사용하면 메모리의 특정 위치를 가리켜 그 위치의 값을 수정하거나 참조할 수 있습니다.

---

2. 연결 리스트란 무엇인가?

연결 리스(Linked List)는 데이터를 저장하는 기본 자료 구조 중 하나로, 각 데이터 요소가 노드 형태로 연결된 방식으로 구성됩니다. 배열과 달리 메모리 공간을 연속적으로 사용할 필요가 없으며, 노드를 동적으로 추가하고 삭제할 수 있어 효율적인 메모리 사용이 가능합니다.

 

연결 리스트의 구성 요소

• 노드(Node): 연결 리스트의 기본 단위로, 두 가지 주요 요소를 포함합니다.
  • 데이터(Data): 노드가 저장하는 실제 데이터.
  • 포인터(Next Pointer): 다음 노드의 주소를 가리키는 포인터로, 이를 통해 노드들이 순차적으로 연결됩니다.
• 헤드(Head): 연결 리스트의 첫 번째 노드를 가리키는 포인터입니다. 리스트의 시작 지점을 나타내며, 이를 통해 리스트의 모든 노드에 접근할 수 있습니다.

 

연결 리스트의 종류

• 단일 연결 리스트(Singly Linked List):
  • 각 노드는 하나의 다음 노드만을 가리키는 포인터를 가지고 있습니다.
  • 마지막 노드는 NULL을 가리켜 리스트의 끝을 나타냅니다.
  • 구조:

Head -> Node1 -> Node2 -> Node3 -> NULL

 

• 이중 연결 리스트(Doubly Linked List):
  • 각 노드는 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 가지고 있습니다.
  • 리스트의 양방향 탐색이 가능하여, 삽입과 삭제가 좀 더 유연하게 이루어집니다.
  • 구조:

NULL <- Node1 <-> Node2 <-> Node3 -> NULL

 

• 원형 연결 리스트(Circular Linked List):
  • 마지막 노드가 첫 번째 노드를 가리키도록 연결되어 원형 구조를 이루는 리스트입니다.
  • 헤드를 통해 시작점으로 다시 돌아올 수 있습니다.
  • 단일 연결 리스트와 이중 연결 리스트 모두 원형 구조로 변형할 수 있습니다.
  • 구조 (단일 원형 연결 리스트 예시):

Head -> Node1 -> Node2 -> Node3 -> Head

 

 

---

 

3. 배열과 연결 리스트의 차이점

연결 리스트는 동적 메모리 할당을 통해 크기를 유동적으로 변경할 수 있기 때문에, 배열의 고정 크기 제한을 극복할 수 있습니다. 또한 삽입과 삭제가 매우 효율적입니다. 중간에 노드를 추가하거나 삭제할 때 나머지 노드를 이동시키지 않고, 포인터만 적절히 수정하면 됩니다.

• 배열: 고정된 크기로 선언되며, 중간에 요소를 삽입하거나 삭제할 때 비효율적입니다.
  • 삽입과 삭제가 비효율적이다.
    중간에 요소를 삽입하려면 그 뒤의 모든 요소들을 한 칸씩 이동시켜야 하고, 삭제하려면 삭제 후에 뒤의 요소들을 앞으로 이동시켜야 합니다. 따라서 삽입과 삭제의 시간 복잡도는 O(n)이 됩니다.
  • 고정된 크기
    배열의 크기가 고정되어 있으므로, 처음 선언할 때 배열의 크기를 충분히 예측하여 지정해야 합니다. 만약 크기가 부족할 경우 새로운 더 큰 배열을 만들어서 데이터를 복사해야 하고, 메모리 낭비가 발생할 수 있습니다.
  • 메모리의 낭비
    데이터가 가변적인 경우, 배열의 크기를 너무 크게 선언하면 사용되지 않는 공간이 메모리 낭비로 이어질 수 있습니다.
• 연결 리스트: 크기가 동적으로 조정 가능하며, 삽입과 삭제가 빠릅니다.
  
  • malloc: 메모리 동적 할당을 위한 함수
  • realloc: 할당된 메모리 크기를 동적으로 재조정할 때 사용하는 함수
  • free: 동적 할당된 메모리를 해제하는 함수

---

4. 포인터와 자기참조 구조체

포인터는 자기 자신을 가리키는 자기참조 구조체에서도 사용됩니다. 연결 리스트에서 각 노드는 다음 노드를 가리키는 포인터를 포함하며, 이러한 방식으로 노드들이 서로 연결됩니다.

• 자기참조 구조체
  • 자기참조 구조체는 구조체 안에 자기 자신과 동일한 구조체 타입의 포인터가 포함된 구조체입니다.
  • 자기참조 구조체는 주로 연결리스트와 같은 동적데이터 구조를 구성하는 데 사용됩니다.
• 자기 참조 구조체의 선언
  • 자기참조 구조체를 선언할 때는 구조체의 이름을 포인터로 선언하여 구조체 내부에 포함합니다.
  • 예시:

typedef struct Node {
    int data;
    struct Node* next;  // 자기참조 포인터: 다음 노드를 가리킴
} Node;

위 예제에서 Node 구조체는 data와 next를 멤버로 가지고 있으며, next는 다음 Node의 주소를 가리킵니다.

 

• 포인터와 자기참조 구조체의 관계
  • 포인터는 자기참조 구조체에서 다음 노드를 가리키는 용도로 사용되며, 데이터가 추가되거나 삭제될 때 연결을 재구성하는 데 중요한 역할을 합니다. 
  • 동적 메모리 할당을 통해 새로운 노드를 생성하고, 포인터를 통해 노드들을 연결하여 구조체 간의 연결을 만듭니다.
  • 예를 들어, 위 코드의 append 함수는 새로운 노드를 추가할 때 동적 메모리 할당을 통해 next 포인터가 다음 노드를 가리키도록 설정합니다.
• 포인터와 동적 메모리 할당
  • malloc과 free
    연결 리스트와 같은 동적 데이터 구조에서는 malloc 함수를 사용하여 런타임에 메모리를 할당하고, free 함수를 사용하여 할당된 메모리를 해제해야 합니다.
  • 예시

struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->data = 5;
free(node);  // 메모리 해제

 

포인터와 자기참조 구조체는 메모리와 데이터 구조를 효율적으로 관리할 수 있는 C 언어의 중요한 기능입니다. 포인터는 메모리 주소에 직접 접근할 수 있게 하여 데이터 구조를 유연하게 조작할 수 있게 해주고, 자기참조 구조체는 동적 크기의 데이터 구조를 구성하는 데 유용합니다. 이를 통해 연결 리스트와 같은 자료구조를 효과적으로 구현할 수 있습니다.