.

선형 리스트는
stack
queue
list

연결리스트는
stack
queue
list
노드를 사용

비선형 리스트는
tree
graph

연결 리스트(단순 연결 리스트, 단순 선형 연결 리스트)
LinkedList

data link(주소)
[ Node ]
Node의 특징
데이터를 가지고 있지 않으면
노드로써의 의미가 없다.
link는 주소를 저장하는 변수이고
data에는 정수, 실수, 문자, 문자 배열 등이 들어간다.

하나의 이름에 각기 다른 데이터 타입을 묶어서 사용할 수 있는 변수가 존재 --> 구조체
c에서 자료구조를 구현하는데 사용하는 것이 구조체이다.
노드를 선언하는데 구조체가 필수

preNode CurrentNode nextNode
data link data link data link
20 30 Null
현 주소 10 20 30

link에는 다음 값이 있는 주소를 보관한다.

struct listNode{
char data[4];
struct listNode * link;
};

연결 할 수 있는 기준 노드를 생성
이 연결 할 수 있는 노드에는 데이터(x)
유일하게 가질 수 있는 것은 주소만이다.
이러한 노드를 자료구조에서 head node 라고 한다.

헤드 노드 정의(기준 노드가 된다)
struct headNode{
listNode * headNode;
};

연결리스트는 헤드 노드와 노드의 정의로부터 시작

새로운 노드를 추가하는 방법
1. 자기의 앞 노드가 될 이름이 가지고 있는 주소를 받아 온다.
2. 그리고 나서 받은 주소를 통해 연결한다.
3. 자기의 주소를 자신의 뒤 노드에게 전달
4. 자신의 주소를 가지고 있는 뒤 노드와 연결

삽입할 노드를 주닙
새 노드의 데이터 필드에 값을 저장
새 노드의 주소(링크(값을 저장
리스트의 앞 노드에 새 노드이 주소를 전달하여 연결

데이터를 삽입하는 위치에 따라
맨 처음, 중간, 맨 마지막 이렇게 삽입할 수 있다.
자료구조 구현은 1. 각각의 위치에 따라서 함수를 생성하는 방법
2. 하나의 함수로 구현하는 방법이 존재

<InsertLinkedList.h>
#pragma once

typedef struct ListNode {
char data[4];
struct ListNode* link;
} listNode;

typedef struct {
listNode* head;
} linkedList_h;

linkedList_h createLinkedList_h(void);
void freeLinkedList_h(linkedList_h L);
void printList(linkedList_h L);
void insertFirstNode(linkedList_h L, char x);
void insertMiddleNode(linkedList_h L, listNode pre, char x);
void insertLastNode(linkedList_h L, char x);

<InsertLinkedList.c>
#define _CRT_SECURE_NO_WARNINGS //경고가 일어나느 부분을 사용자에게 알리지 않고 그냥 실행

#include <string.h>
#include <stdlib.h>
#include "InsertLinkedList.h"

//메모리 할당 및 해제 함수, 출력 함수, 삽입 함수 구현
linkedList_h createLinkedList_h(void) {
linkedList_h L;
L = (linkedList_h*)malloc(sizeof(linkedList_h));
L->head = NULL;
return L;
}

//메모리 해제 함수
void freeLinkedList_h(linkedList_h L) {
listNode p;
while (L->head != NULL) {
p = L->head;
L->head = L->head->link;
free(p);
p = NULL;
}
}

//출력 함수
void printList(linkedList_h L) {
listNode p;
printf("L = (");
p = L->head;
while (p != NULL) {
printf("%s", p->data);
p = p->link;
if (p != NULL) printf(", ");
}
printf(") \n");
}

//삽입 함수
void insertFirstNode(linkedList_h L, char x) {
listNode newNode;
newNode = (listNode)malloc(sizeof(listNode));
strcpy(newNode->data, x);
newNode->link = L->head;
L->head = newNode;
}

//pre 노드 뒤에 삽입
void insertMiddleNode(linkedList_h L, listNode pre, char x) {
listNode newNode;
newNode = (listNode*)malloc(sizeof(listNode));
strcpy(newNode->data, x);
if (L->head == NULL) {
newNode->link = NULL;
L->head = newNode;
}
else if (pre == NULL) {
newNode->link = L->head;
L->head = newNode;
}
else {
newNode->link = pre->link;
pre->link = newNode;
}
}

//마지막에 삽입
void insertLastNode(linkedList_h L, char x) {
listNode newNode;
listNode temp;
newNode = (listNode*)malloc(sizeof(listNode));
strcpy(newNode->data, x);
newNode->link = NULL;
if (L->head == NULL) {
L->head = newNode;
return;
}
temp = L->head;
while (temp->link != NULL) temp = temp->link;
temp->link = newNode;
}

<sampleLink.c>
#include <stdio.h>
#include "InsertLinkedList.h"

int main(void) {
linkedList_h* L;
L = createLinkedList_h();
printf("(1) 공백 리스트 생성하기! \n");
printList(L);

printf("\n(2) 리스트에 [수] 노드 삽입하기! \n");
insertFirstNode(L, "수");
printList(L);

printf("\n(3) 리스트 마지막에 [금] 노드 삽입하기! \n");
insertLastNode(L, "금");
printList(L);

printf("\n(4) 리스트 첫 번째에 [월] 노드 삽입하기! \n");
insertFirstNode(L, "월");
printList(L);

printf("\n(5) 리스트 공간을 해제하여 공백 리스트로 만들기! \n");
freeLinkedList_h(L);
printList(L);

return 0;

}