[자료구조] 연결 리스트

1. 연결 리스트

 

1) 정의 : 자료가 순서를 가지고 나열된 자료구조를 이야기 한다.

 

2) 리스트의 표현

 

ⓐ 배열 이용

- 이 방식은 리스트의 각 원소마다 배열의 원소에 대응시킨다.

- A[k]를 읽거나 교체하는 연산은 상수시간이 걸리지만, 삽입과 삭제 연산은 순차매핑을 유지하기 위해 원소의 이동을 필요로 하므로 많은 시간이 소요된다.

* 순차 매핑 : 배열이 메모리의 연속적인 공간을 차지함

 

ⓑ 연결 리스트 이용

- 연결 리스트란 화살표로 표시되는 링크를 가진 노드의 순서 리스트 이다.

- 첫번째 노드를 가르키는 포인터의 이름이 연결 리스트의 이름이다. 

* 연결리스트의 노드들은 메모리에 순차적으로 놓여있지 않을 수 있다.

 

연결 리스트 그림

 

🟡 포인터를 이용하여 연결 리스트 표현하기

- 하나의 노드는 데이터를 갖고있는 데이터 필드와 다음 원소를 가르키는 포인터로 구성된다.

- 연결 리스트를 구현하기 위해선 구조체를 이용한다.

 

typedef struct list_node* list_pointer; // list노드의 주소를 저장할 포인터를 선언함
typedef struct list_node {
	int data; //데이터가 들어감
	list_pointer link; //다음 노드의 주소를 저장할 포인터
};

list_pointer ptr = NULL; //헤드노드는 NULL

list_pointer create(void) {
	list_pointer first, second;
	first = (list_pointer)malloc(sizeof(list_node));  //첫번째 노드의 동적메모리 할당
	second = (list_pointer)malloc(sizeof(list_node)); //두번째 노드의 동적메모리 할당
	second->link = NULL;
	second->data = 20;
	first->link = second;
	first->data = 10;
	return first;
}

* typedef, 구조체, 포인터, 동적메모리할당에 대해 알아야 이해가 가능함.

 

🟡 노드의 삽입

- 그림을 떠올려 가면서 코드를 작성하는 것이 좋다

노드의 삽입

void insert(list_pointer node, int data) 
{
	list_pointer temp;
	temp = (list_pointer)malloc(sizeof(list_node));
	if (temp == NULL) {
		fprintf(stderr, "The memory is full\n");
		exit(1);
	}
	temp->link = node->link;
	node->link = temp;
	temp->data = data;


}

 

🟡 노드의 삭제

void delete_node (list_pointer back, list_pointer trail , list_pointer node) {
	if (trail) //첫번째 원소를 제거하는경우
	{
		trail->link = node->link;
	}
	else {
		back = back->link;
	}
	free(node);

}

🟡 노드의 출력