[자료구조] 단일 연결 리스트

단일 연결 리스트

포인터를 이용해 단방향적으로 다음 노드를 가리킴

하나의 구조체 안에 두 개의 변수가 들어감 : data, next (다음 위치를 가리키는 pointer)

일반적으로 연결 리스트의 시작 노드를(Head)라고 하며 별도로 관리

마지막(끝) 노드의 다음 위치 값으로는 NULL을 넣음

단일 연결 리스트의 형태

#include <stdio.h>
#include <stdlib.h> //!< 동적할당 사용

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

Node *head;

int main(void)
{
	head = (Node*)malloc(sizeof(Node));
	Node *node1 = (Node*)malloc(sizeof(Node));
	node1->data = 1;
	Node *node2 = (Node*)malloc(sizeof(Node));
	node2->data = 2;
	head->next = node1;
	node1->next = node2;
	node2->next = NULL;
	Node *cur = head->next;
	while(cur!=NULL)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
	system("pause");
	return 0;
}

결과
1 2

 

연결 리스트의 삽입 및 삭제

연결 리스트 삽입 과정

연결 리스트 삭제 과정

#include <stdio.h>
#include <stdlib.h> //!< 동적할당 사용

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

Node *head;

//!< 연결리스트 삽입 과정
void addFront(Node *root, int data)
{
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = root->next;
	root->next = node;
}

//!< 연결리스트 삭제 과정
void removeFront(Node *root)
{
	Node *front = root->next;
	root->next = front->next; //!< front = 삭제하고자 하는 것
	free(front);
}

//!< 연결리스트 메모리 해제
void freeAll(Node *root)
{
	Node *cur = head->next;
	while(cur != NULL)
	{
		Node *next = cur->next;
		free(cur);
		cur = next;
	}
}

//!< 연결리스트 전체 출력 함수
void showAll(Node *root)
{
	Node *cur = head->next;
	while(cur != NULL)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
}

int main(void)
{
	head = (Node*)malloc(sizeof(Node));
	head->next = NULL;
	addFront(head, 2);
	addFront(head, 1);
	addFront(head, 7);
	addFront(head, 9);
	addFront(head, 8);
	removeFront(head);
	showAll(head);
	freeAll(head);
	system("pause");
	return 0;
}


결과
9 7 1 2

 

연결 리스트 구현에 있어서 주의점

삽입 및 삭제 기능에서의 예외사항 처리 필요

삭제할 원소가 없는데 삭제하는 경우, 머리(head) 노드 자체를 잘못 넣은 경우 등 체크 필요