Linked List (링크드 리스트) 이해 및 기본적인 생성

 

 

Linked List란 다음 그림과 같은 구조로 포인터를 이용하여 List를 만들어 내는 것이다.

 

즉 데이터와 link를 이용하여 하나의 배열 형태로 이루어 져 있지만 실제로는 List형태로 연결되어 있는 것이다.

 

 

List를 사용하면 Array를 이용할 때 정적인 방법으로 코드 작성시에 Array 사이즈를 지정해 주던것을 동적인 방법으로 만들어 줄 수 있고,

 

구조체의 내용에 따라 다양한 data를 이용하여 List를 만들어 낼 수 있다.

typedef struct node {
	int data;
	struct node *next;
}node;

 

위의 구조대로 node를 만들어 낸다면 구조체의 선언을 위와 같이 해주면 되고, 만약에 int형 data말고도 추가적으로 더 넣고 싶은게 있다면

 

구조체에 넣어주기만 하면 된다. 그렇게 되면 node 타입의 노드들이 List형태로 연결되는 자료구조를 만들어 낼 수 있다.

 

삽입시에도 원하는 노드 다음노드에 포인터를 연결해 주면 되고, 삭제시에도 원하는 노드에 연결되어 있는 포인터를

 

그다음 노드로 연결시켜주면 된다.

 

 

 

그렇다면 기본적인 Linked List를 생성하는 코드를 보도록 하겠다.

 

코드는 파일로 저장되어있는 20개의 정수를 읽어와 Linked List로 연결하는 프로그램 이다.

 

 

List를 생성할 때에는 기본적으로 두가지 기능을 할 수 있는 함수를 만들어 주었는데

 

하나는 새로운 노드를 생성하는 함수, 그리고 하나는 생성된 노드를 원하는 List의 마지막 노드에 연결시키는 함수 이다.

 

동적할당인 malloc을 이용해서 node* type의 메모리를 allocation해주고, 초기 data는 0, next link는 Null로 초기화 시켜준다.

node* newnode(int data)
{
	node* n = (node*)malloc(sizeof(node));
	n->data = data; // 받아온 data를 node의 data에 저장
	n->next = NULL; // node의 next 포인터는 일단 NULL로 저장한다

	return n; // 생성된 node의 주소를 return
}

 

파라미터로 받아오는 새로운 node 주소와 header 주소를 이용해서 header에 연결된 노드들의 제일 마지막 노드를 찾고, 새로운 노드를 연결시켜준다.

void LinkNode(node* h, node* n)
{
	node* p = h->next;
	if(h->next == NULL) // head->next의 node가 NULL일때 (첫번째 노드일때)
	{ 
		h->next = n; // head의 next주소를 n으로 설정
	}
	else // head의 node가 NULL이 아닐 때 (첫번째 노드가 아닐때)
	{
		while(p->next != NULL)
		{
			p=p->next; // p의 next주소가 NULL일때까지 검색한뒤 마지막 값을 p에 저장한다.
					   // 즉, 마지막 node의 주소를 p에 저장한다.
		}
		p->next = n; // 마지막 node의 next값을 새로 들어온 n의 주소값으로 저장한다.
	}
}

다음과 같은 두개의 함수를 이용해서 만들어 주었다.

node* makeLL(void)
{
	node* h = (node*)malloc(sizeof(node)); // Linked List 포인터
	node* s;
	int i=0, buf;	
	FILE *file_open;

	h->data = 0;
	h->next = NULL; // header를 초기화 시켜준다. data는 0, next주소는 NULL
	

	file_open = fopen("Random_num.txt","rt");
	
	// 파일의 값을 모두 읽어와 각 노드에 저장하면서 Linked List로 연결해 준다
	while(fscanf(file_open,"%d\n",&buf) != EOF) {
		//printf("%d ",buf);
		s = newnode(buf); // buf값과 newnode함수를 이용해서 node를 생성해준다.
		
		LinkNode(h,s); // head와 생성된 node를 넘겨주어 head에 연결된 Linked List에 노드를 연결해준다.
	}

	
	fclose(file_open);

	return h;
}

 

main함수 내에서 node* 형식의 변수를 하나 만들어 주고 그 포인터변수에 makeLL() 함수를 붙여 주었다.

 

makeLL() 함수 내에서는 fscanf()를 통해 파일로 부터 정수를 읽어오고, 매번 newnode()와 LinkNode() 를 Call하는것을 볼 수 있다.

 

파일에서 읽어온 정수인 buf를 파라미터로 넘겨 새로운 노드를 생성하고, 생성된 노드를 header 포인터 정보와 함께 넘겨

 

제일 마지막에 연결시키는 구조이다.