C언어의 기초 - 연결 리스트 Linked List

연결 리스트를 사용하면 배열을 선언하고 특정 상황에 이용할 때 생기는 문제점들을 해결할 수 있다.

가령 배열의 크기를 넘어가는 입력에 대한 처리 같은 유동적인 할당을 하고 싶을 때 사용하면 좋다.

 

물론 배열의 크기를 바꾸어 다시 선언하거나 동적 할당을 받았다면 realloc 으로 크기를 늘려도 된다.

하지만 런타임 중 수정하기 어려운 문제가 있고, realloc 의 경우 만드려는 충분한 메모리가 없다면 

실패할 수 있고, 복사하는 시간이 추가적으로 들기도 한다.

그렇기 때문에 메모리 상의 남은 공간 아무데나 할당 받아 숫자를 저장하고 주소를 외우는 방식이 편리하기도 하다.

 

그래서 힙 기반의 링크드 리스트를 살펴본다.

 

Head 는 배열의 가장 앞에 있는 녀석으로 첫 요소의 주소를 가리키는 정보만이 중요하다.

만약 첫 요소가 없다면 다음 주소는 0x0(NULL)이 되므로 빈 배열이 된다.

 

만약 단방향 링크드 리스트가 필요하다면 (다음 주소는 알지만 이전 주소는 모르는 링크드 리스트)

양방향에서 prev에 해당하는 주소만 수행하지 않으면 충분하다.

 

1. 양방향 링크드 리스트

 

Insert 함수는 구조체 배열 Student 에 학번을 저장하고 다음 학생의 주소를 저장한다. 

기존 구성원들과 학번을 비교하면서 새로운 학생 정보를 넣는다.

학번 순으로 넣기 때문에 나보다 학번이 큰 (높은) 사람이 나오면 그 앞에 넣고,

나보다 큰 사람이 없다면 가장 뒤에 (다음 주소가 0x0인 사람 뒤에) 넣는다.

 

Delete 함수도 비슷하다. 

search_id_node 라는 함수를 따로 구현할 수도 있지만 head를 따라가면서 찾아봐도 좋다.

찾았다면 바로 앞 번호와 뒷 번호의 next, prev 를 수정해주면 된다.

만약 마지막에 있다면 뒷 번호의 prev를 수정할 필요가 없다.

중요한 것은 할당을 해제해줘야 메모리가 부족하지 않을 수 있다.

//양방향 링크드 리스트

#include <stdio.h>
#include <conio.h>
#include <malloc.h>


typedef struct st{
	int id;
    struct st * next;
    struct st * prev;
}Student;

Student Head;

//배열에 데이터를 넣는데 학번 순으로 넣음, 중복 허용 안함
int Insert(Student * head, Student * d)
{
	while(1)
	{
		if ((head->next == (Student*)0x0) || (d->id < head->next->id))
		{
        	Student * p  = calloc(1, sizeof(Student));
            //할당실패
            if (!p) return -1;
            
            *p = *d;
            p->prev = head;
            p->next = head->next;
            if (head->next!=0x0) head->next->prev= p;
            head->next = p;
			return 1;
		}
		//중복 학번 입력 안함
		if (d->id == head->next->id) return -2;

		head = head->next;
	}

	return -1;
}

//삭제
int Delete(Student * head, int id)
{
	//학번 있는지 찾고 주소 return 없으면 0리턴하는 함수
	Student * p = Search_Id_Node(head, id);
	if (!p) return -1;
    //바로 앞요소 주소 수정
	p->prev->next = p->next;
    //마지막 요소가 아니라면 뒤 요소 prev 주소 수정
	if (p->next!=0x0) p->next->prev = p->prev;
    //할당해제
	free(p);
	return 1;



}

 

 

 2. 다중 연결

요소가 2개 이상이고 요소 별로 정렬되거나 연결된 형태로 구현할 수도 있다.

이럴 경우 한 번에 처리하기는 어렵고 각 요소별로 insert 를 시키는게 편하다.

하지만 각 요소별로 insert 할 때마다 새로운 할당을 해줘선 안된다. 

공간을 2배로 사용하기 때문에 같은 함수 안에서 한 번 할당 후 각자 수행하여 연결하는 것이 좋다.

 

삭제는 연결된 링크만큼의 처리가 필요하다.

여기선 Height 와 Id 를 연결해놨기 때문에 각각에 해당하는 delete함수를 만들고, 하나를 삭제하려면

height 와 id link를 따라가면서 앞 뒤를 연결시키도록 구현하였다.

#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <malloc.h>

typedef struct _score 
{
	int id;
	int height;
	struct _score  * nid; 
	struct _score  * nheight; 
}Student;

Student Head;

int Insert(Student * head, Student * d)
{
	Student * temp = head;
	Student * p = 0x0;

	for (;;)
	{
		if ((head->nid == 0x0) || (d->id < head->nid->id))
		{
			p = calloc(1, sizeof(Student));

			if (p == 0x0) return -1;
			*p = *d;

			p->nid = head->nid;
			head->nid = p;
			break;
		}

		if (d->id == head->nid->id) return -2;

		head = head->nid;
	}

	head = temp;

	for (;;)
	{
		if ((head->nheight == 0x0) || (d->height < head->nheight->height))
		{
			p->nheight = head->nheight;
			head->nheight = p;
			return 1;
		}

		head = head->nheight;
	}
	
}

int Delete_Id(Student * head, int id)
{
	Student * tmp = head;
	while (1) {
		if (head->nid == 0x0) return -1;
		if (head->nid->id == id) {
			Student * p = head->nid->nid;
			head->nid = p;
			break;
		}
		head = head->nid;
	}
	head = tmp;
	while (1) {
		if (head->nheight == 0x0)return -1;
		if (head->nheight->id == id) {
			SCORE* p = head->nheight->nheight;
			free(head->nheight);
			head->nheight = p;
			return 1;
		}
		head = head->nheight;
	}

}



void Delete_One_Height(Student * head, int height, int id)
{
	Student * tmp = head;
	while (1) {
		if (head->nheight == 0x0) return;
		if (head->nheight->id == id && head->nheight->height == height) {
			Delete_Id(tmp, id);
			return;
		}
		head=head->nheight;
	}

}

int Delete_Height(Student * head, int height)
{
	Student * tmp = head;
	int flag = -1;
	while (1) {
		if (head->nheight == 0x0) return flag;
		if (head->nheight->height == height) {
			Delete_One_Height(tmp, height, head->nheight->id);
			flag = 1;
		}
		else
			head = head->nheight;

	}



}

 

 

자료구조에서 스택과 큐는 굉장히 중요하지만 선입후출과 선입선출의 개념만 알고 있다면

쉽게 구현이 가능하기도 하고, c++에 넘어가서는 그마저도 직접 구현하지 않고 불러와 사용하기 때문에

글로는 적지 않고 사용해야겠다.