[ C++ ] 연결 리스트

연결 리스트

---

1. 리스트

• 배열 기반 리스트

  • 장점
    • 배열로 만들었으므로 특정한 위치의 원소에 즉시 접근 가능
  • 단점
    • 데이터가 들어갈 공간을 미리 메모리에 할당해야 함
    • 원하는 위치로의 삽입이나 삭제가 비효율적

• 단일 연결 리스트
  • 일반적으로 연결 리스트의 시작 노드를 헤드(Head)라고 하며 별도로 관리
  • 포인터를 이용해 단방향으로 다음 노드 지정

  • 다음 노드가 없는 끝 노드의 다음 위치 값으로 NULL

  • 장점
    • 삽입과 삭제가 배열에 비해서 간단 (데이터를 추가하거나 삽입 시, 포인터 값만 바꾸면 됨)
  • 단점
    • 특정 인덱스로 즉시 접근하지 못하며, 원소를 차례대로 검색
    • 추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비

#define _CRT_SECIRE_NO_WARNINGS

#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;

}

2. 연결 리스트 삽입, 삭제

연결리스트 삽입과정

연결리스트 삭제과정

#define _CRT_SECIRE_NO_WARNINGS

#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;

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));

//처음 main 함수에서 head 의 next 값이 NULL
head->next = NULL;

// addFront()하게 되면 node2의 next는 root(head)의 next가 되고 root(head)의 next는 node를 가리키게 된다.
addFront(head, 2);

// 그다음 addFront()하게 되면 node2의 next가 root(head)의 next로 node1을 가리키고, root(head)의 next가 node1를 가리킴
addFront(head, 1);

addFront(head, 7);

addFront(head, 9);

addFront(head, 8);

// removeFront()에서 head 뒤에 있는 Node2가 연결 해제 되어, 그 뒤에 노드로 연결됨
removeFront(head);

//Root(head)의 next가 front의 next를 가리키는데 front의 next는 node2의 next를 가리키기 때문에 node1과 이어지며 결과적으로 head와 node1이 이어진다.
showAll(head);

freeAll(head);

system("pause");

return 0;

}