보통 컴파일 타임이라고 하는 것의 개념은 실행시 프로그램 실행 도중이 아닌 제작당시에 실행되어야 하는 작업의 실행 시점을 의미합니다. 런타임에 결정되는 것이 아니기에 변수가 컴파일 타임에 초기화되면 소스코드를 바꾸기 전까지는 이 초기화된 상태와 크기를 바꿀 수 없습니다. 배열의 경우 메모리 효율이 안좋은데 컴파일 타임에 미리 메모리 공간을 일정 크기만큼 예약해두는 체제라서 그렇습니다. 그래서 동적 메모리 할당이 필요해지고 이를 자료구조에서 연구한 것이 연결리스트입니다. 연결리스트는 자료 대입이 필요할때마다 메모리의 일정 공간을 초기화해서 노드로 만들고 이 노드들을 연결시켜서 자료의 덩어리로 만듭니다. 같은 자료형의 배열과 같이 자료의 덩어리가 되는데 차이점은 필요할때마다 메모리를 할당하는 구조라, 메모리 활용에 낭비가 없다는 사실입니다.
언어마다 다른 구문으로 연결리스트를 만드는데, 최소구조는 (1) 대입할 자료형으로 된 변수 하나 (2) 다음 노드를 가리키는 방편 입니다. 자바에서는 클래스를 만들어 표현하고 C에서는 구조체를 만들어 표현합니다. 특별히 C에서 (2)를 처리하는 구문은 포인터 변수인데, 연결리스트의 종류에 따라 하나에서 두개의 포인터 변수를 두어 각각의 노드가 이어지는 구조를 표현하죠. (1)의 경우 범용으로 된 자료형으로 만드는 방법도 있으나 일단 이글에서는 정수형 변수 하나만 두는 형태로 해설해보겠습니다.
연결리스트의 형태는 아래와 같은 노드들의 묶음입니다.

보시는 바와 같이 START가 의미하는 첫노드에 DATA가 저장된 부분과, 다음 노드를 가리키는 Next가 저장된 부분이 최소 구조입니다. 프로그래머는 일단 연결리스트를 초기화하는 코드를 작성하면 그 위치의 메모리 주소가 할당되고 거기에 DATA를 가진 변수와 다음 노드를 가리키는 포인터 변수인 Next가 줄줄히 연결된 비엔나 소시지 (?)처럼 추상화됩니다. 물론 메모리 상의 물리적인 작동은 프로그래머가 쉽게 알아챌 수 없는 0과 1의 묶음 또는 전류의 인가, 해제의 복잡한 아날로그적인 작동인데요. 일단 위의 구조를 알아두면 좋습니다.
메모리 상태는 아래처럼 도식화됩니다.

0x80017이라는 메모리 주소는 연결리스트 초기화할때와 노드 추가할때 할당이 되구요. 실재적으로는 메모리 주소들의 순서보다는 무질서하게 그때그때 할당되는 원리지만 다음 노드를 가리키는 Next라는 포인터 변수에 의해 대입된 메모리 주소가 다음 노드를 가리켜서 서로 이어지게 됩니다.
구조체를 써서 이를 표현하는 설계도를 그리면 아래와 같습니다.
struct Node
{
int DATA;
struct Node *Next;
}
typedef struct Node *NODE;
이렇게 선언한 구조체를 변수로 지정하고 DATA와 Next 변수에 접근해서 자료를 대입시키고 연결리스트에 노드로 추가하고 제거하는 등의 오퍼레이션을 실행합니다.
struct Node *node1;
node1 = (struct *Node)malloc(sizeof(struct Node));
node1->DATA = 1;
node1->Next = NULL;
위에 주목할 부분은 malloc() 으로 동적 할당하는 부분과 node1 변수에서 구조체 필드를 참조하는 화살표 모양의 문법이구요. 여기에 하나 더 중요한 것은 node1->Next 에 NULL을 할당했다는 것입니다. NULL로 할당한 것은 아직 다음 노드가 없다는 의미이구요. 두번째 노드를 할당하면 이 값이 그 두번째 노드를 가리키게 되며 그 다음 노드 또한 그 다음의 다음 노드를 가리키게 되어있습니다. 메모리 주소를 직접 입력하기보다, 새로 생성한 노드 변수에서 node1->Next = node2; 와 같이 할당합니다.
자료구조의 장점은 이렇습니다.
(1) 동적 메모리 할당 구조라 메모리 낭비가 적음
(2) 위와 같은 도식을 코드화했으므로 효율적인 구조 표현이 가능해짐
(3) 자료 추가와 삭제가 상대적으로 쉬움
(4) 대다수의 규모가 큰 프로그램들은 연결리스트를 자주 씀
단점은 아래와 같습니다.
(1) 특정 자료형을 대입할때 불필요한 포인터 변수도 함께 선언되서 배열 변수를 꽉 채워 운용하는 것이 늘 가능한 경우와 비교하면 같은 수의 데이터 처리시 메모리가 더 필요하게 될 수도 있습니다.
(2) 구조체로 표현되므로 실행시간이 길어질 개연성이 있습니다.
연결리스트로 가능한 오퍼레이션으로는 이런 것들이 있습니다.
(1) 노드 생성
(2) 노드 추가
(3) 노드 삭제
(4) 노드 탐색
(5) 노드 검색
(6) 노드 병합
이중에서 노드 추가는
(a) 연결리스트 맨앞에
(b) 연결리스트 맨끝에
(c) 특정한 지정된 위치에
가능하구요. 노드 삭제도 비슷합니다. 노드 병합은 연결리스트들끼리 병합하는 것으로, 연결리스트 1과 연결리스트 2가 각각 n개 노드, m개 노드를 가지고 있었다면, 병합된 결과는 n+m의 노드를 가지게 됩니다.
연결리스트는 크게 세가지 종류가 있습니다.
(1) 단일 연결리스트 – 노드들이 하나의 포인터 변수를 가지고 있습니다. 그래서 다음 노드만 가리키게 되어 있구요. 이전 노드 참조는 안됩니다.
(2) 이중 연결리스트 – 노드들이 두개의 포인터 변수를 가지고 있습니다. 이전 노드 참조가 가능합니다.
(3) 환영 연결리스트 – 첫 노드와 마지막 노드가 연결되어 있습니다.
이중에서 환영 연결리스트는 (1)과 (2)의 특징을 모두 가지게 할 수도 있습니다.
단일 연결리스트에 노드가 추가되고 삭제되는 순서는 아래처럼 예시됩니다.

단일 연결리스트에서 맨처음에 노드를 추가하는 알고리즘입니다.
(1) 새 노드를 생성
(2) 새 노드->DATA = 대입할 자료
(3) 만약 START가 NULL 이면 새 노드->Next = NULL 또는 새 노드->Next = START
(4) START = 새 노드
맨마지막에 추가하는 알고리즘입니다.
(1) 새 노드를 생성
(2) 새 노드->DATA = 대입할 자료
(3) 새 노드->Next = NULL
(4) (4)와 (5) 반복: START가 NULL 이면 START = 새 노드 또는 TEMP = START
(5) (반복 이어서) TEMP->Next가 NULL이 아닌 동안 TEMP = TEMP->Next
(6) TEMP->Next = 새 노드
특정한 위치에 추가하는 알고리즘입니다.
(1) TEMP = START
(2) i 가 pos 보다 작은 동안 반복: TEMP = TEMP->Next
(3) (반복 이어서) 만약 TEMP = NULL 이면 “오류 메시지 출력”
(4) 새 노드 생성
(5) 새 노드->DATA = 대입할 자료
(6) 새 노드->Next = TEMP->Next
(7) TEMP->Next = 새 노드
노드 삭제 알고리즘입니다.
(1) 만약 START->DATA는 삭제할 자료와 같으면
(2) TEMP = START
(3) START = START->Next
(4) TEMP를 해제 (삭제됨)
(5) HOLD = START
(6) HOLD->Next->Next가 NULL이 아닐 동안 반복
(7) (반복 이어서) TEMP = HOLD->Next
(8) (반복 이어서) HOLD->Next = TEMP->Next
(9) (반복 이어서) TEMP 해제 (삭제됨)
(10) HOLD = HOLD->Next
(11) 만약 HOLD->Next->DATA 가 삭제할 데이터와 같으면
(12) TEMP = HOLD->Next
(13) TEMP 해제 (삭제됨)
(14) HOLD->Next = NULL
#include<stdio.h>
#include<malloc.h>
// 리스트를 위한 구조체 선언
struct Node
{
int DATA;
struct Node *Next;
}*start;
// 새 리스트 생성
void create_list(int data)
{
struct Node *q, *tmp;
// 동적 메모리 할당
tmp= (struct Node*)malloc(sizeof(struct Node));
tmp->DATA = data;
tmp->Next = NULL;
if (start == NULL) // 리스트가 비어있으면
start=tmp;
else
{ /* 마지막에 자료 추가 */
q=start;
while(q->Next != NULL)
q=q->Next;
q->Next=tmp;
}
}
// 새 자료를 맨처음에 추가
void add_to_beginning(int data)
{
struct Node *tmp;
tmp = (struct Node*)malloc(sizeof(struct Node));
tmp->DATA=data;
tmp->Next=start;
start=tmp;
}
// 새 자료를 특정 위치에 추가
void add_to_any_pos(int data, int pos)
{
struct Node *tmp, *q;
int i;
q=start;
// 추가할 위치 탐색
for(i = 0; i < pos - 1; i++)
{
q = q->Next;
if(q == NULL)
{
printf ("\n\n %d 개수보다 작은 개수만 있습니다.",pos);
}
}
tmp = (struct Node*)malloc(sizeof (struct Node));
tmp->Next = q->Next;
tmp->DATA=data;
q->Next=tmp;
}
// 특정 자료 삭제
void deleteIt(int data)
{
struct Node *tmp, *q;
if (start->DATA == data)
{
tmp = start;
start = start->Next; // 맨앞 자료 삭제
free(tmp);
}
q = start;
while(q->Next->Next ! = NULL)
{
if (q->Next->DATA == data)
{
tmp=q->Next;
q->Next=tmp->Next;
free(tmp);
}
q=q->Next;
}
if(q->Next->DATA == data)
{
tmp=q->Next;
free(tmp);
q->Next=NULL;
}
printf ("\n\n %d가 없습니다.",data);
}
void main()
{
start=NULL;
create_list(10);
add_to_beginning(12);
add_to_any_pos(24, 1);
deleteIt(12);
}