4 minute read

Linked list : 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법

Linked list는 데이터를 저장하는 data field와 다른 노드의 주소를 저장하는 포인터 변수를 가지고 있는link field가 있다.

1. 포인터

  • Pointer variable(or pointer) : 메모리의 주소를 저장하기 위한 변수

포인터의 선언

포인터 변수의 타입은 가리키는 변수의 자료형과 일치해야 한다.

float *pf; // float 형 변수를 가리킬 목적의 포인터 pf 선언
int* pi; // int 형 변수를 가리킬 목적의 포인터 pi 선언 - 이 방법이 자료형과 변수가 구분되어 우수하다.

char* p, q, r; // char* 변수 p와 char 변수 q, r을 선언
char *p, *q, *r // char* 변수 p, q, r 선언 - 한 문장으로 여러 개의 포인터 변수를 선언할 수 있다.

포인터는 사용하기 전에 반드시 초기화해야 한다.

int i = 10;
int* p;
p = &i;

포인터의 활용

  • 역참조 연산자(*) : 포인터가 가리키는 메모리의 내용을 추출하거나 변경할 때 사용한다.
*p = 10
i = 10 // *p와 i는 완전히 동일하며, 두 문장은 동일하다.

어떤 포인터가 다른 포인터를 가리킬 수 있다.

2. 동적 메모리 할당

Static memory allocation(정적 메모리 할당) : 프로그램이 컴파일될 때 변수나 객체가 사용할 메모리를 미리 할당하는 방식

int x; // int 형 변수 i를 정적으로 할당
int* p; // 포인터 변수 p를 정적으로 할당
int A[10]; // 길이가 10인 배열을 정적으로 할당

예를 들어 위와 같은 문장이 실행되면 int 형의 크기(4byte)의 메모리가 자동으로 만들어진다.

x = 10;
p = &x;

이후 위와 같은 문장을 이용하여 이 변수를 사용할 수 있다. 정적 메모리 할당은 다음과 같은 특징이 있다.

  • 필요한 메모리의 크기가 프로그램이 컴파일 될 때 결정되고 프로그램의 실행 중에 크기를 변경할 수 없다.
  • 변수를 선언만 하면 자동으로 메모리가 할당되고 해당 프로그램 블록이 끝나면 자동으로 제거된다.(개발자는 메모리의 제거에 신경 쓸 필요가 없다.)

하지만 입력의 크기를 미리 알 수 없는 경우에 고정된 크기의 메모리를 미리 할당해야 하기 때문에 배열을 정적으로 할당하는 것은 경우에 따라 비효율적일 수 있다. 만약 할당된 크기보다 더 큰 입력이 들어온다면 처리하지 못 할 것이며, 더 작은 입력이 들어온다면 남은 메모리 공간이 낭비될 것이다. 이 문제를 해결하기 위해 dynamic memory allocation(동적 메모리 할당) 방법이 제시된다.

동적 메모리 할당은 다음과 같은 특징이 있다.

  • 동적 메모리 할당 라이브러리 함수를 사용해 메모리를 생성하고, 필요 없으면 해제해야 한다.(개발자가 메모리의 생성과 해제를 직접 관리해야 하는 번거로움이 있다.)
  • 프로그램 실행 중에 필요한 메모리의 크기를 결정하고 시스템으로부터 할당받아서 사용할 수 있다.(필요한 만큼만 할당하고 반납하므로 메모리를 매우 효율적으로 사용할 수 있다.)

동적 메모리 할당 라이브러리 함수

동적으로 메모리를 할당하여 주소를 반환하는 함수는 다음과 같다.

void* malloc(int size);

void* calloc(int num, int size);

malloc() 함수 : size 크기의 메모리 블록을 할당하고, 이 메모리 주소의 시작 주소를 byte 단위로 반환한다.

calloc() 함수 : 배열 요소의 크기는 size 바이트이고 개수는 num인 배열 형식의 메모리를 할당하고, 이 메모리의 시작 주소를 byte 단위로 반환한다.

char* pc = (char*)malloc(5); // 문자 5개를 저장할 공간 할당

int* pi = (int*)malloc(sizeof(int)); // int를 저장할 공간 할당

malloc() 함수와 calloc() 함수가 반환하는 void* 형이므로 적절한 자료형으로 형변환해서 사용해야 한다.

메모리를 동적으로 해제하는 함수는 다음과 같다.

void free(void* ptr);
free(pc);
free(pi);

free() 함수 : 동적으로 할당되었던 메모리 블록을 시스템에 반납한다.

ptr은 할당되었던 메모리 블록을 가리키는 주소값이다. 할당과 달리 해제시에는 자료형을 명시할 필요가 없다.

포인터와 동적 메모리 할당

int* pi = (int*)malloc(sizeof(int)*10);
Polynomial* pa = (Polynomial*)malloc(sizeof(Polynomial));

pi[3] = 10; // 동적 할당된 메모리를 배열처럼 사용
pa -> degree = 5; // 동적 할당된 다항식 구조체의 멤버 변경

free(pi);
free(pa);

구조체 배열도 동일한 방법으로 동적으로 할당하고 해제할 수 있다. 다항식 구조체 Polynomial의 배열을 동적으로 할당하여 다항식을 10개를 저장하는 예를 보자.

Polynomial* list = (Polynomial*) malloc(sizeof(Polynomial)*10);
list[0].degree = 0; // 0번째 다항식의 degree를 0으로 초기화
list[9].coef[2] = 3.1; // 9번째 다항식의 2번째 계수를 3.1로 설정
...
free(list); // Poly 배열을 동적으로 해제

여기서 list는 구조체 배열이고, list[k]는 하나의 다항식 구조체이다.

3. 연결 리스트

  • 연결 리스트 : 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법
  • 연결된 표현 : 데이터와 링크로 구성되어 있으며, 링크가 노드들을 연결한다. 줄(링크, 포인터)로 연결된 상자(데이터)라고 생각할 수 있다.
  • 연결된 표현 스택, 큐, 리스트, 덱, 트리, 그래프 등 여러 가지의 자료구조를 구현하는 데 널리 사용된다.
  • 데이터들이 메인 메모리상에서 한군데 모아져 있는 것이 아니라 어디에나 흩어져서 존재한다.
  • 각각의 데이터는 다음 데이터를 가리키는 줄을 가지고 있어 순서를 유지한다.
  • 첫 데이터에서부터 순서대로 줄을 따라가면 모든 데이터를 방문할 수 있다.

배열에 대한 연결 리스트의 장점

Array   Linked list
처음에 선언한 크기로 고정된다. 메모리 메모리를 할당할 수 있는 한 자료의 제한이 없다.
자료를 추가할 때 그 위치 이후의 모든 자료들을 뒤로 하나씩 복사한 후 그 자리에 자료를 넣어야 한다. 삽입 데이터 B와 C 사이에 데이터 N을 삽입하고자 하면, B에서 N을 가리키도록 하고 N이 C를 가리키도록 링크만 수정하면 된다.
데이터를 옮겨야 한다. 삭제 데이터들을 연결하는 줄만 수정하면 된다.
한꺼번에 많은 공간을 할당해야 한다.(정적 메모리 할당) 메모리 할당 데이터 저장을 위한 메모리 공간이 필요할 때마다 동적으로 만들어 쉽게 추가할 수 있다.
쉽다. 구현 어렵다. 오류가 발생하기 쉽다.

연결 리스트 구조

연결 리스트 용어 정의
연결 리스트 서로 연결된 노드들의 집합
노드 데이터 필드와 링크 필드로 구성된다.
데이터 필드 정수나 구조체의 자료형의 데이터가 들어간다.
링크 필드 다음 노드의 주소를 저장하는 포인터 변수를 담고 있어 다음 노드를 가리킨다.
헤드 포인터 연결 리스트에서 첫 번째 노드의 주소를 저장하는 포인터

연결 리스트는 첫 번째 노드를 알아야 링크로 매달려 있는 모든 노드에 순차적으로 접근할 수 있기 때문에 첫 번째 노드의 주소를 반드시 저장해야 한다. 마지막 노드는 링크 필드의 값을 NULL로 설정하여 이 노드가 마지막임을 알린다.

연결 리스트의 종류

  • 단순 연결 리스트
  • 원형 연결 리스트
  • 이중 연결 리스트

You may also enjoy