연결리스트란?
연결리스트는 노드라는 구조체로 이루어진 저장하는 선형 자료구조이다. 노드는 자신이 가리키는 데이터와 다음 노드의 주소값을 갖는 포인터 변수로 구성되어 있다.
다음 그림과 같이 노드 하나당 데이터 값을 저장하고 다음 노드를 가리키는 구조로 이루어져 있다.
배열과 차이점
배열도 선형 자료구조라는 점에서 동일한 특성을 나타내지만 일정한 크기의 메모리를 할당받아 사용하는 배열과 달리 연결리스트는 내가 필요할 때마다 메모리를 할당하고 해제하여 메모리 관리를 효율적으로 할 수 있다는 장점이 있다.
그리고 배열 중간에 새로운 데이터를 삽입하려면 기존 데이터를 한칸씩 뒤로 이동해아 한다는 번거로움이 있지만 연결리스트는 다음 그림과 같이
삽입하려는 앞 뒤 노드만 바꿔주면 되기 때문에 O(1)의 시간복잡도로 삽입할 수 있다.
연결리스트의 종류
단일 연결리스트: 연속 노드로 구성된 가장 단순한 연결 형태의 데이터 구조이다. 노드에 데이터와 다음 노드의 주소를 저장한다.
이중 연결리스트: 노드의 구성요소에 이전 노드를 가리키는 포인터를 추가하여 양방향 접근이 가능한 데이터 구조이다.
원형 연결리스트: 마지막 노드가 헤드노드의 주소를 가리켜 마지막 노드까지 탐색이 끝났으면 다시 처음부터 탐색이 가능하도록 한다.
head노드와 tail노드
구현하기에 앞서 head 노드와 tail 노드에 대해서 알 필요가 있다.
Node* head = NULL; Node* tail = NULL;head 노드는 항상 첫 번째 노드를 카리킨고 tail 노드는 마지막 노드를 가리킨다. 첫 노드를 head에 연결하고 마지막 노드를 tail 노드에 연결함으로써 양쪽에서 데이터를 접근할 수 있게 구현이 가능하다.
단일 연결리스트 구현
가장 쉬운 역순 저장하는 단일 연결리스트를 구현해보겠다. 3 2 1 순으로 데이터가 저장되면 1 2 3순으로 출력 되는 구조이다.
먼저 노드를 생성해야 한다.
노드는 자신의 데이터와 다음 노드를 가리킨다.
노드 구조체
typedef struct Node { int data; struct Node* next; }Node;
노드 생성
노드를 동적할당 받아 생성하고 newNode의 다음 노드에는 NULL값을, data에는 값으로 초기화 시켜준다.
그리고 만들어진 newNode의 주소를 return해준다.
노드 삽입
첫 생성 노드라면 head에 newNode를 연결하고 종료시켜주고 아닐 경우 생성된 newNode에 head노드를 연결시켜주고 head가 가리키는 값을 newNode로 바꿔준다. 이 경우 나중에 들어온 값을 head가 계속 가리키는 것이다.
노드 탐색
함수에 head노드와 찾고 싶은 target을 전달하여 target값이 저장된 노드를 찾을 때까지 순차적으로 탐색하여 찾은 경우 그 노드의 주소를 찾지 못하면 NULL값을 반환해준다.
노드 삭제
함수 종료 시 동적할당했던 노드들을 head노드부터 순차적으로 탐색하여 메모리를 해제해준다.
전체 코드
#include<stdlib.h>
#pragma warning(disable:4996)
typedef struct Node {
int data;
struct Node* next;
}Node;
Node* craete_node(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->next = NULL;
newNode->data = data;
return newNode;
}
Node* search_Node(Node* head, int target) {
Node* curNode = head;
if (curNode == NULL)
return NULL;
while (curNode) {
if (curNode->data == target)
return curNode;
curNode = curNode->next;
}
return curNode;
}
void insert_node(Node** head ,Node*newNode) {
if (*head == NULL) {
*head = newNode;
return;
}
newNode->next = *head;
*head = newNode;
}
void print(Node* head) {
Node* curNode = head;
while (curNode != NULL) {
printf("%d ", curNode->data);
curNode = curNode->next;
}
puts("");
}
void _free(Node* head) {
Node* delNode;
Node* curNode = head;
while (curNode) {
delNode = curNode;
curNode = curNode->next;
free(delNode);
}
}
int main() {
Node* head = NULL;
while (1) {
char command;
int data;
printf("명령 입력 : ");
scanf("%c", &command);
switch (command) {
case 'I': //삽입
printf("추가할 데이터 : ");
scanf("%d", &data);
Node* newNode = craete_node(data);
insert_node(&head, newNode);
break;
case 'S': // 탐색
printf("탐색할 데이터 : ");
scanf("%d", &data);
Node* node = search_Node(head, data);
if (node == NULL)
printf("찾는 데이터가 없습니다!\n");
else {
printf("Node data : %d\n", node->data);
}
break;
case 'P': // 출력
printf("데이터 출력 : ");
print(head);
break;
case 'E': //반복문 종료
_free(head);
return 0;
break;
}
getchar();
}
_free(head);
return 0;
}