C/C++ 연결 리스트(Linked List)

Six Root·2023년 8월 3일

C++ 공부

목록 보기

9/10

배열과 리스트의 장단점

배열

장점
메모리의 형태가 덩어리 형태로 연속적으로 할당되어, 특정 원소에 접근을 할 때 인덱스를 통해 굉장히 빠르게 접근할 수 있다.
배열의 크기가 커도 접근 속도는 항상 일정하다.
단점
원소를 추가하거나 삭제하려고 할 때 데이터의 이동하는 횟수가 너무 많아질 수 있다.

데이터가 정렬된 상태를 유지해야 할 경우에 단순히 맨 뒤에다가 원소를 추가하는 방법은 사용할 수가 없다.

연결 리스트

장점
메모리의 형태가 노드 형태로 비연속적으로 할당되어, 원소를 추가하거나 삭제하려고 할 때 데이터의 이동이 필요하지 않고 연결 구조만 바꿔주면 된다.
단점
원소에 접근하려면 헤드(head)부터 차례대로 접근하는 수 밖에 없어서 접근 속도가 느리다.

데이터의 추가와 삭제가 빈번한 프로그램이라면 연결 리스트를 사용하는게 좋고,
삽입과 추가는 없고 접근만 하는 프로그램이라면 배열을 사용하는게 좋다.

연결 리스트(Linked List)의 특징

가변배열과 마찬가지로 데이터를 계속해서 추가할 수 있지만, 데이터를 관리하는 방식이 가변배열과는 다르다.
배열은 메모리가 연속적이라는 특징이 있지만, 리스트는 데이터가 연속적이지 않고 떨어져있다.
그때 그때 필요한 만큼 힙 메모리 영역을 생성한다.
데이터 하나를 저장하는 단위를 노드(Node)라고 한다.
첫번째 노드의 주소를 갖고 있는 것을 헤드(Head) 라고 한다.
첫번째 영역에 데이터 뿐만 아니라 다음 노드의 주소도 들어있어서 서로가 서로를 연결하는 구조이다.
첫번째 시작주소만 알면 다음 그 다음 노드도 알 수 있게 된다.

단일 연결 리스트(Singly Linked List)

구조체 선언

값을 저장할 value와 다음 노드의 주소를 저장할 next를 선언해준다.

typedef struct node 
{
  int value; // 값 저장
  struct node* next; // 다음 노드의 주소를 저장
}node;

node* head = NULL; // 시작노드의 주소를 저장할 head 포인터 지정

노드 맨 앞 삽입

설명
맨 앞 노드는 항상 head 가 가리키고 있기 때문에 head 다음 노드를 새로운 노드가 가리키게 하고 head 가 새로운 노드를 가리키게 하면 된다.
순서

newNode를 선언하고 동적할당 해준 후 값을 입력받고, next 값을 NULL로 한다.
head가 가리키는 노드를 newNode의 next가 가리키게 한다.
head가 newNode를 가리키게 한다.

#include <stdio.h>
#include <stdlib.h>

// 구조체 생략

node* head = NULL;

void insert_node_front() 
{
  node* newNode = (node*)malloc(sizeof(node));
  scanf("%d", &newNode->value);
  newNode->next = NULL;
  if (head == NULL)
  {
    head = newNode;
    return;
  }
  newNode->next = head;
  head = newNode;
}

노드 순회 및 출력

설명
head 부터 차례대로 값을 저장할 변수를 만들고 그 변수의 값을 출력한다.
순서

방문하는 각 노드의 주소를 담을 curNode 변수를 선언한다.
head 부터 시작해서 curNode->next 가 NULL이 나올 때 까지 계속 방문하면서 출력한다.

#include <stdio.h>
#include <stdlib.h>

// 구조체 생략

node* head = NULL;

void displayNode()
{
  if (head == NULL)
  {
    printf("연결 리스트가 구성되지 않아 출력할 값이 없습니다.\n");
    return;
  }
  node* curNode = head; // 방문할 노드의 주소를 저장할 변수 생성, 시작은 head부터.
  while (curNode->next != NULL)
  {
  	printf("%d ", curNode->value);
    curNode = curNode->next; // 다음 노드를 방문한다.
  }
  printf("%d\n", curNode->value); // 마지막 노드가 출력되게 끔
}

노드 맨 뒤 삽입

설명
연결 리스트를 마지막 노드까지 순회하고 새로운 값을 마지막 노드가 가리키게 한다.
순서

newNode를 선언하고 동적할당 해준 후 값을 입력받고, next 값을 NULL로 한다.
head 가 NULL 일 때 예외처리 해준다.
순회하는데 사용할 curNode 변수를 선언한다.
curNode->next 가 NULL이라면 curNode->next에 newNode의 주소값을 저장한다.

// 헤더 생략
// 구조체 생략

node* head = NULL;

void insert_node_rear()
{
  node* newNode = (node*)malloc(sizeof(node));
  scanf("%d", &newNode->value);
  newNode->next = NULL;
  
  if (head == NULL)
  {
    head = newNode;
    return;
  }
  node* curNode = head;
  while (curNode->next != NULL)
  {
    curNode = curNode->next; // 다음 노드를 방문한다.
  }
  curNode->next = newNode; // 마지막 노드에 새 노드를 삽입한다.
}

노드 전체 삭제

설명
연결 리스트 구조를 유지하기위해 head 의 다음 노드를 계속 head로 저장해 가면서 차례대로 삭제해 나간다.
순서

head 가 NULL 이면 삭제할 필요가 없기 때문에 예외처리 해준다.
삭제할 노드를 저장할 delNode 를 선언하고 head 노드를 저장해준다.
head 를 head->next 로 바꿔주고 delNode를 삭제한 후 delNode에 head 를 저장한다.

// 헤더 생략
// 구조체 생략

node* head = NULL;

void removeAllNode()
{
  if (head == NULL)
  {
    printf("삭제할 데이터가 없습니다.\n");
    return;
  }
  node* delNode = head;
  while (head != NULL)
  {
    head = head->next;
    free(delNode);
    delNode = head;
  }
}

노드 정렬 삽입 (오름차순)

설명
4가지 경우를 생각할 수 있다.
첫번째, head 가 NULL 일 때
두번째, 가장 작은 수를 삽입할 때 (head 의 값이 새로운 노드보다 클 때)
세번째, 중간에 삽입할 때 (새로운 값이 순회하는 노드의 값보다 작을 때)
네번째, 가장 큰 수를 삽입할 때 (마지막까지 노드가 순회해도 새로운 노드의 값보다 작을 때)
순서

newNode를 선언하고 동적할당 해준 후 값을 입력받고, next 값을 NULL로 한다.
head 가 NULL 이면 head 값에 newNode 를 저장한다.
head 의 값이 새로운 노드보다 크다면 newNode->next 가 head->next 를 가리키고 head 가 newNode 를 가리키게 한다.
curNode 를 선언해주고, 만약 curNode 가 newNode 보다 더 크다면 이전 값을 newNode 에 연결해야 하기 때문에 prevNode 를 선언해 준 후 둘 다 head 부터 저장한다.
head 의 '다음 값' 부터 순회하면서 newNode 의 값과 비교해 나간다.
prevNode 는 curNode 보다 한 박자 늦게 순회해야 하기 때문에 삽입 구문 뒤에 다음 노드를 방문하도록 해준다.
마지막까지 순회해도 curNode 의 값이 newNode 보다 작다면 curNode->next 가 newNode 를 가리키게 한다.

// 헤더 생략
// 구조체 생략

node* head = NULL;

void insert_node_sort()
{
  node* newNode = (node*)malloc(sizeof(node));
  scanf("%d", &newNode->value);
  newNode->next = NULL;
  // case 1. head 가 null일 때
  if (head == NULL)
  {
    head = newNode;
    return;
  }
  // case 2. 가장 작은 값을 삽입
  if (head->value > newNode->value)
  {
    newNode->next = head->next;
    head = newNode;
    return;
  }
  // case 3. 중간에 삽입
  node* curNode, * prevNode; // 이전 노드 저장할 prevNode 도 선언
  curNode = prevNode = head;
  while (curNode->next != NULL)
  {
    curNode = curNode->next; // 값이 가장 작을 때는 위에서 이미 걸러 냈기 때문
    if (curNode->value > newNode->value)
    {
      newNode->next = curNode;
      prevNode->next = newNode;
      return;
    }
    prevNode = prevNode->next;
  }
  // case 4. 가장 큰 값을 삽입
  curNode->next = newNode;
}

이중 연결 리스트 (Doubly Linked List)

구조체 선언

값을 저장할 value와 다음 노드를 저장할 next, 이전 노드를 저장할 prev 변수를 선언해준다.

typedef struct dNode
{
  int value;
  struct dNode* next;
  struct dNode* prev;
}dNode;

dNode* dHead = NULL;

이중 연결 리스트의 역순 연결

설명
head 부터 순회해 가면서 prev 와 next 를 swap 해주면 역순으로 연결된다.
순서

순회하는데 사용할 curNode 변수를 선언한다.
swap 할 때 사용할 임시변수 temp 변수를 선언한다.
노드가 없거나 하나인 경우 역순 연결 할 필요가 없기 때문에 예외처리 해준다.
curNode 가 NULL 일 때까지 순회하며 swap 해준다.
마지막 노드까지 swap 을 하게되면 curNode->prev 가 NULL 이 되는데 그럼 head 가 curNode 를 가리키게 한다.

// 헤더 생략
// 구조체 생략

dNode* head = NULL;

void reverse_dNode()
{
  dNode* curNode = head;
  dNode* temp;
  // 노드가 없거나, 하나인 경우 예외 처리
  if (head == NULL || head->next == NULL)
   return;
   
  while (curNode != NULL)
  {
    // swap
    temp = curNode->next;
    curNode->next = curNode->prev;
    curNode->prev = temp;
    if (curNode->prev == NULL) // 마지막 노드 일 때 head 가 가리키게 해준다.
    {
      head = curNode;
      return;
    }
    curNode = curNode->prev; // swap 한 이후라 prev 로 다음 노드로 이동
  }
}

Six Root

언리얼 전문가가 될 때까지 (중요한 건 꺾이지 않는 마음)

이전 포스트

C/C++ 트리(Tree) 구조

다음 포스트

C/C++ 스택(Stack)과 큐(Queue)

1개의 댓글

happy

2023년 8월 3일

유익한 글이었습니다.

답글 달기