연결 리스트 (linked list)

연결 리스트 (linked list)

배열과 달리 각각의 요소가 포인터를 사용하면서 다음 요소의 위치를 가리킨다.

포인터를 사용하여 자료를 연결하는 다른 자료구조에는 스택, 큐, 트리, 그래프 등이 있다.

연결리스트는 메모리상 아무 곳에나 위치하는 자료들을 서로 연결하여 하나로 묶는 방법이다.

C에서는 서로를 연결하는 줄을 포인터로 구현한다. 

연결 리스트를 사용하면 중간에 자료를 추가하여야할때,

배열은 추가하는 자리부터 한칸씩 밀어내면서 전부 수정해줘야하지만 연결리스트는 연결하던 줄(포인터)만 수정하면된다.

삭제할때도 마찬가지로 줄(포인터)만 수정하면 된다.

또한 연결 리스트는 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어 쉽게 추가할 수 있다.

그러나 배열에 비해 상대적으로 구현이 어렵고 오류가 나는것을 조심해야한다.

연결 리스트 구조

연결리스트는 노드와 리스트로 이루어져있다.

연결 리스트는 노드들의 집합이다. 노드는 데이터 필드(data field)와 링크 필드(link field)로 구성되어 있다.

데이터 필드에는 저장하려는 데이터가 들어간다,

즉 정수값이나 이름, 문자, 전화번호가 포함된 구조체등 복잡한 데이터도 저장이 가능하다.

링크 필드에는 다른 노드를 가리키는 포인터가 저장된다. 

이 포인터를 이용하여 다음 노드로 건너갈 수 있다. 연결 리스트에서는 연결리스트의 첫 번째 노드를 알아야

전체 노드에 접근할 수 있는데 이때 첫 번째 노드를 가리키는 변수를 헤드 포인터(head pointer)라고 한다.

연결 리스트의 이름은 헤드 포인터의 이름과 같다.

노드가 하나도 없을 때에는 헤드 포인터는 NULL값을 가지게 되고 공백 연결 리스트라고 한다.

헤드 포인터, 데이터 필드, 링크 필드, 마지막은 NULL

 

자기 참조 구조체

struct NODE {
	int data;
    struct NODE *link;	//현재 구조체를 가리킬 수 있는 포인터
};

일반적으로 항목의 개수를 미리 예측할 수 없는 경우에 자체 참조 구조체를 정의하고 동적으로 기억 장소를 할당받아 이들을 포인터로 연결하여 자료 구조를 구성한다. 

자기 참조 구조체는 연결 리스트나 트리를 구성할 때 많이 등장한다.

tydef struct NODE {	//typedef로 자기 참조 구조체를 새로운 자료형 NODE로 정의하여 사용
	int data;
    struct NODE *link;
} NODE;

 

연결 리스트 예시

tydef struct NODE {	//typedef로 자기 참조 구조체를 새로운 자료형 NODE로 정의하여 사용
	int data;
    struct NODE *link;
} NODE;

우선 위와 같이 노드의 구조를 구조체를 이용하여 정의한다.

이때 노드의 구조는 정의했지만 아직 노드는 생성된 것이 아니다.

일반적으로 연결 리스트에서는 필요할 때마다 동적 메모리 할당을 이용하여 노드를 동적으로 생성한다.

NODE *p1;				//새로운 자료형 NODE를 가리키는 포인터 p1선언
p1=(NODE *)malloc(sizeof(NODE));	//NODE를 가리키는 포인터p1에게 NODE의 크기만큼 동적할당

동적 메모리를 할당받아 노드가 된다.

다음으로 만들어진 노드에 데이터를 저장하고 링크 필드를 NULL로 설정한다.(마지막인경우)

p1->data=10;
p1->link=NULL;

혹은 연결해야할 노드가 더 존재하는 경우에는 link에 NULL을 설정하는것 대신 다음과 같이 사용한다.

NODE *p2;	//NODE를 가리키는 포인터 p2를 만든다.
p2=(NODE *)malloc(sizeof(NODE));	//동일하게 동적 메모리를 할당받아 노드를 만든다.
p2->data=20;
p2->link=NULL;	//p2가 마지막이므로 NULL로 설정한다.
p1->link=p2;	//NULL로 설정되었던 p1의 링크 필드가 p2를 가리키며 연결하는 줄이 된다.

노드를 더 생성하여 연결하려면 반복하여 사용하면된다.

하지만 주의해야할점은 동적 메모리 할당을 하였으므로 사용이 끝나면 반드시 메모리를 해제하여야한다.

free(p1);
free(p2);