Data Structure의 목표는 메모리의 효율적 사용이다.
연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조
각 노드는 데이터 필드와 다음 노드에 대해 참조를 포함하는 노드로 구성
링크 필드는 다음 노드의 주소를 저장 (첫번째 노드 주소는 따로 저장필요)
마지막 노드의 next필드는 NULL을 저장하여 연결리스트의 끝임을 표시한다.
다른 데이터의 이동 없이 중간에 삽입이나 삭제가 가능
길이의 제한이 없다 (동적 크기)
랜덤 엑세스가 불가능
void push(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void insertAfter(struct Node* prev_node, int new_data){
if (prev_node == NULL){
printf("이전 노드가 NULL이 아니어야 합니다.");
return;
}
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
void append(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node *last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL){
*head_ref = new_node;
return;
}
while(last->next != NULL){
last = last->next;
}
last->next = new_node;
return;
head 포인터는 마지막 노드를 가르킨다
head는 마지막 노드를 , head의 link는 첫 노드를 가르켜서 리스트의 처음과 마지막에 노드를 삽입하는 연산이 편리해진다.
노드를 리스트의 첫 부분에 삽입하는 연산의 경우
리스트의 뒷부분에 삽입하는 경우
#include <stdio.h>#include <stdlib.h>typedef int element;
typedef struct { // 노드 타입
element data;
struct ListNode *link;
} ListNode;
// 리스트의 항목 출력
void print_list(ListNode* head)
{
ListNode* p;
if (head == NULL) return;
p = head->link;
do {
printf("%d->", p->data);
p = p->link;
} while ( p! = head );
printf("%d->", p->data); // 마지막 노드
}
// 앞부분 삽입
ListNode* insert_first(ListNode* head, element data)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = data;
if (head == NULL) {
head = node;
node->link = head;
}
else {
node->link = head->link;
head->link = node;
}
return head;
}
// 뒷부분 삽입
istNode* insert_last(ListNode* head, element data)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = data;
if (head == NULL) {
head = node ;
node->link = head;
}
else {
node->link = head->link;
head->link = node;
head = node;
}
return head; // 변경된 헤드 포인터 반환
}
// 메인
int main(void)
{
ListNode *head = NULL;
// list = 10->20->30->40
head = insert_last(head, 20);
head = insert_last(head, 30);
head = insert_last(head, 40);
head = insert_first(head, 10);
print_list(head);
return 0;
}
/* 실행결과
10->20->30->40->
*/
https://opentutorials.org/module/1335/8940
https://gyoogle.dev/blog/computer-science/data-structure/Linked List.html
https://opentutorials.org/module/1335/8821