자료구조)링크드리스트-단일 링크드 리스트

링크드 리스트 Linked List란?

각 노드가 데이터와 포인터를 가지고 한줄로 연결되어있는 방식으로 데이터를 저장하는 자료구조로 포인터를 통해 다음노드와 연결시켜 사용하는 자료구조다.

 

단일 연결 링크드리스트

 

링크드 리스트의 장단점

링크드 리스트는 배열과 자주 비교되는데 링크드 리스트와 배열의 차이는 이러하다

링크드 리스트

배열처럼 연속적으로 저장하는것처럼보이지만 메모리상에는 연속적으로 위치하지 않고 포인터를 통해 링크한다.

 

장점

• 삽입 및 중간 수정이 매우 편하다.

단점

• 항목 접근 속도가 오래 걸린다 특히 뒤로있을수록 단일 연결 리스트의 경우 앞에서부터 탐색해 가야하기때문에 오래걸린다
• 메모리 연산으로 접근 불가능하다
• 포인터를 저장하는 공간을 따로 가져야 해서 메모리를 더 잡아먹는다

vs

배열

메모리상에 물리적으로 연속된 메모리의 묶음이다

 

장점

• 항목 접근이 빠르다(메모리 연산으로 접근이 가능하다)
• 동일한 데이터 타입을 연속적으로 저장할 수 있다

단점

• 동적 할당이 아닐 경우 크기가 고정되어있고 배열의 크기를 지정해야 한다
• 삽입과 수정이 매우 복잡하다 처음과 중간에 데이터를 추가하려면 버퍼를 통해 밀거나 새로 할당해야 한다

 

 

링크드 리스트의 종류

출처 :연결 리스트 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

단일 연결 리스트

단일 연결 리스트는 각 노드에 자료 공간과 포인터 공간이 있고 한 방향으로만 다음 노드를 가리킨다

 

이중 연결 리스트

단일 연결 리스트와 비슷하지만 포인터 공간이 2개이고 앞의 노드와 뒤의 노드를 같이 가리킨다 그렇기에 양방향으로 탐색이 가능하다

원형 연결 리스트

마지막 tail 부분에서 끝나는 게 아니라 다시 head를 가리키는 연결 리스트

 

 

링크드 리스트 노드 구조

단일 연결 리스트의 경우 다음의 노드를 참조하는 포인터 공간이 한개인 반면 이중연결 리스트의 노드경우 양쪽다 참조하기위해 포인터공간이 2개다

 

 

단일 연결 리스트의 구현

 

해당 코드는 씹어먹는 C 언어 - <20 - 2. 메모리 동적 할당 + 메모리 갖고 놀기> (modoocode.com)를 참조하여 만들었습니다.

 

조건

1. 대부분의 예제는 head를 비우지만 우리는 그냥 데이터를 집어넣을 겁니다

2. 그렇기에 head 뒤로만 연결되는  링크드 리스트가 됩니다

 

연결 리스트 노드 구현 - 구조체 생성

struct Linked{
	struct Linked* link_point_next;//다음 노드 주소
	struct Linked* this_Addr; //내주소
	int data;//데이터
};

나중에 출력할 때 이전 노드가 앞 노드의 주소를 제대로 참조하는지 보기 위해  this_addr을 추가

 

 

struct Linked* head_Create_node(int insert_data) { //머리 노드생성
	
	struct Linked* header = (struct Linked*)malloc(sizeof(struct Linked));
	//데이터대입
	header->this_Addr = header;
	header->data = insert_data;
	//기본으로 테일을 가르치게함 
	header->link_point_next = NULL;

	return header;
}

처음엔 Null을 가르킴

 

노드 삽입 구현

struct Linked* link_Create_node(struct Linked* before_node, int insert_data) {
	//새롭게 노드를 만들어서 삽입

	//앞노드가 가르키던 주소를 버퍼에저장
	struct Linked* before_node_buffer = before_node->link_point_next;
	//노드를 동적으로 생성
	struct Linked* make_node = (struct Linked*)malloc(sizeof(struct Linked));

	//데이터 대입 및 앞노드가 가르키던 주소를 대입 
	make_node->data = insert_data;
	make_node->link_point_next = before_node_buffer;
	make_node->this_Addr = make_node;
	//앞노드의 주소를 이제 자신에게 가르키게 함
	before_node->link_point_next = make_node;

	//리턴
	return make_node;

}

 

 

struct Linked* before_node_buffer = before_node->link_point_next;

1. 이전 노드가 가리키고 있던  다음 노드의 주소를 담아둡니다

 

 

 

 

struct Linked* make_node = (struct Linked*)malloc(sizeof(struct Linked));

2. 노드를 생성합니다

 

 

 

make_node->link_point_next = before_node_buffer;

before_node_buffer에 있던 이전 노드의 주소를  make_node주소에 담습니다

 

 

make_node->this_Addr = make_node; make_node->data = insert_data;  

매개변수로 받은 데이터를 생성한 노드에 대입합니다

 

 

before_node->link_point_next = make_node;

head_node의 주소부분을 makenode를 가리키게 합니다.

 

 

전체 코드 

#include<stdio.h>	//printf
#include<stdlib.h> //malloc & free

struct Linked{
	struct Linked* link_point_next;//다음 노드 주소
	struct Linked* this_Addr; //내주소
	int data;//데이터
};


struct Linked* head_Create_node(int insert_data) { //머리 노드생성
	
	struct Linked* header = (struct Linked*)malloc(sizeof(struct Linked));
	//데이터대입
	header->this_Addr = header;
	header->data = insert_data;
	//기본으로 테일을 가르치게함 
	header->link_point_next = NULL;

	return header;
}

struct Linked* link_Create_node(struct Linked* before_node, int insert_data) {
	//새롭게 노드를 만들어서 삽입

	//앞노드가 가르키던 주소를 버퍼에저장
	struct Linked* before_node_buffer = before_node->link_point_next;
	//노드를 동적으로 생성
	struct Linked* make_node = (struct Linked*)malloc(sizeof(struct Linked));

	//데이터 대입 및 앞노드가 가르키던 주소를 대입 
	make_node->data = insert_data;
	make_node->link_point_next = before_node_buffer;
	make_node->this_Addr = make_node;
	//앞노드의 주소를 이제 자신에게 가르키게 함
	before_node->link_point_next = make_node;

	//리턴
	return make_node;

}

void print_node(struct Linked* print_pointer){

	while (print_pointer) {
		printf("노드데이터 : %d  , 이노드의 주소 : %p , 다음노드의 주소:  %p\n", print_pointer->data, print_pointer->this_Addr, print_pointer->link_point_next);
		//출력
		print_pointer = print_pointer->link_point_next;
		//다음 노드로 갱신
	}

}


int main() {

	//노드 생성
	struct Linked* Node_one = head_Create_node(100);
	struct LInked* Node_two = link_Create_node(Node_one, 250);
	struct LInked* Node_trd = link_Create_node(Node_one, 300);
	struct LInked* Node_fo = link_Create_node(Node_one, 40);
	struct LInked* Node_five = link_Create_node(Node_one, 5000);

	//head부터 출력
	print_node(Node_one);


	return 0;
}

 

출력

주소가 잘 링크되어있습니다