(3) 연결리스트

연결리스트 : 데이터와 포인터를 담고 있는 노드들을 한 줄로 연결한 자료구조

자료의 추가와 삭제 시 O(1)의 시간에 가능하다는 장점을 가진다.

그러나 특정 자료를 검색하려면 최대 O(n)의 시간이 걸린다는 단점도 가지고 있다.

단순 연결리스트 구현

#pragma once
#define Element char
#define bool unsigned char
#define true 1
#define false 0

typedef struct list_node *list_pointer;
typedef struct list_node{
	Element data;
	list_pointer link;
}list_node;

void list_insert(list_pointer head, Element e);
void list_delete(list_pointer head, Element e);
list_pointer list_search(list_pointer head, Element e);
bool list_empty(list_pointer head);
void list_show(list_pointer head);

#include 
#include 
#include 
#include 
#include "ll.h"

void main() {
	char			c, e;
	list_pointer	head, p;

	// dummy head 노드 
	head = (list_pointer)malloc(sizeof(list_node));
	head->data = NULL;
	head->link = NULL;

	printf("************ Command *********** \n");
	printf("+: Insert c, -: Delete c   \n");
	printf("?: Search c, S: Show, Q: Quit \n");
	printf("******************************** \n");

	while (1) {
		printf("\nCommand> ");
		c = _getch();
		_putch(c);
		c = toupper(c);
		switch (c) {
		case '+':
			e = _getch();
			_putch(e);
			list_insert(head, e);
			break;
		case '-':
			e = _getch();
			_putch(e);
			list_delete(head, e);
			break;
		case '?':
			e = _getch();
			_putch(e);
			p = list_search(head, e);
			if (p) {
				printf("\n %c is in the list. \n", e);
				printf(" Node address = %p, data = %c, link = %p \n", p, p->data, p->link);
			}
			else printf("\n %c is not in tne list \n", e);
			break;
		case 'S':
			list_show(head);
			break;
		case 'Q':
			printf("\n");
			exit(1);
		default:
			break;

		}
	}
}

void list_insert(list_pointer head, Element e)
{
	list_pointer temp;

	// 새 노드 생성
	temp = (list_pointer)malloc(sizeof(list_node));
	temp->data = e;
	temp->link = NULL;
	// 리스트의 맨 앞에 삽입 
	temp->link = head->link;
	head->link = temp;
}

void list_delete(list_pointer head, Element e)
{
	list_pointer p, temp;

	// e를 찾음
	p = head;
	while (p->link != NULL) {
		if (p->link->data == e) {
			// 삭제 
			temp = p->link;
			p->link = p->link->link;
			free(temp);
			return;
		}
		p = p->link;
	}
	printf("\nData doea not exist !!! \n ");
}

list_pointer list_search(list_pointer head, Element e)
{
	list_pointer p;

	p = head->link;
	while (p != NULL) {
		if (p->data == e) return p;
		p = p->link;
	}
	return NULL;
}

bool list_empty(list_pointer head)
{
	if (head->link == NULL)
		return true;
	else
		return false;
}

void list_show(list_pointer head)
{
	list_pointer p;

	if (list_empty(head)) {
		printf("\nList is Empty\n");
		return;
	}

	printf("\n");
	p = head->link;
	while (p != NULL) {
		printf("%2c", p->data);
		p = p->link;
	}
}

ll.h

ll_main.cpp