title: 자료구조 - 연결 리스트
catalog: true
date: 2019-09-14 14:22:31
subtitle: 자료구조 - 연결 리스트
header-img: "/img/article_header/"
tags:

  • 자료구조
    categories:
  • 자료구조

Goal

  • 자료구조의 한 종료인 연결리스트를 이해한다.
  • 연결리스트를 c언어로 구현한다.

연결리스트란(Linked-List)?

 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결시키면서 자료를 저장하는 자료구조이다. 배열과 비교 했을때, 데이터를 삽입/삭제 할 경우 데이터의 재구성에 용이하다. 반면 특정 위치의 데이터를 검색하기 위해서는 연결리스트를 처음부터 끝까지 순회해야 하므로 비효율적이다.
 연결리스트를 구현하는 방법은 배열을 이용하는 방법과, 구조체와 포인터를 이용하는 방법이 있다.

배열기반의 연결리스트

  • 데이터를 순차적으로 저장하고, 처리할 때는 배열 기반의 리스트를 간단히 이용할 수 있다.
  • 배열로 만들었기 때문에, 특정한 위치의 원소에 즉지 접근가능한 장점
  • 데이터가 들어갈 공간을 미리 메모리에 할당해야하는 단점이 있다.
  • 원하는 위치로의 삽입,삭제 기능을 수행할때는 비효율 적이다.
#include<stdio.h>
#define INF 10000

int arr[INF];
int count = 0;

void addBack(int data) {
    arr[count] = data;
    count++;
}
void addFirst(int data) {
    for(int i = count; i >=1; i--) {
        arr[i] = arr[i-1];
    }
    arr[0] = data;
    count++;
}
void removeAt(int index) {
    for (int i = index; i < count -1; i++) [
        arr[i] = arr[i+1];
    ]
    count--;
}
void show() {
    for(int i = 0; i < count; i++) {
        printf("%d",arr[i]);
    }
}
int main() {
    addFirst(1);
    addFirst(2);
    addFirst(3);
    addBack(4);
    addBack(5);
    show();
    return 0;
}

구조체 포인터 기반의 연결리스트

  • 연결리스트에 데이터를 삽입/삭제할때 효율적이다.
  • 필요할 때마다 메모리 공간을 할당 받는다.
  • 구조체에는 data와 다음 노드주소를 가리키는 next변수가 포함된다.
  • 연결리스트의 마지막 next에는 NULL값이 들어가서 마지막임을 표시한다.
  • 일반적으로, 연결리스트의 시작노드를 Head라고 하며 별도로 관리한다.

image.png

image.png

Node 구조체 선언

연결리스트는 'Node'라는 구조체로 이루어져 있다. 자료를 저장할 공간과 다음 노드를 가리킬 공간이 필요하기 때문에,아래와 같은 구조체로 'Node'를 선언한다.

typedef struct Node {
    int data;
    Node *next;
}Node;

Node 추가하기 기능

  1. 새로운 노드 생성 및 데이터 추가
    image.png

  2. 새로운 노드의 next값에 삽입될 위치의 뒤에 있는 노드 주소를 추가
    image.png

  1. 삽입될 위치의 앞에 있는 node의 next에는 새롭게 추가될 node의 주소를 추가
    image.png
void addFront(Node *root, int data) {
    Node *node = (Node*)malloc(sizeof(Node)); //새로 추가할 노드를 동적으로 할당
    node->data = data; // 새로 추가시킬 노드에 자료 추가
    node->next = root->next; // 새로 추가할 노드의 next에는 삽입하는 앞노드의 next를 추가.
    root->next = node; // 앞노드의 next에는 새로 추가할 노드의 주소를 넣어서 연결시킨다.
}

Node 삭제하기 기능

  1. 삭제할 노드의 위치를 찾는다.
    image.png

  2. 삭제할 노드의 앞에 위치한 node의 next값을 뒷부분에 있는 node의 주소값으로 변환시켜서 연결을 끊는다.
    image.png

  3. 삭제할 노드의 주소값을 free시킨다.
    image.png

void removeFront(Node *root) {
    Node *front = root->next;
    root->next = front->next;
    free(front);
}

전체 연결리스트 출력하기 기능

head노드를 매개변수로 받는다. 그리고 현재노드를 가르키는 cur이라는 node를 생성시켜서 head의 다음 node주소값을 가르키도록 한다.
cur이 NULL이 아닐때까지 data를 출력시키고, cur은 계속 next node를 가르키도록 한다.

void showAll(Node *root) {
    Node *cur = head->next;
    while(cur != NULL) {
        printf("%d",cur->data);
        cur = cur->next;
    }
}

연결리스트 전체 코드

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

typedef struct Node{
    int data;
    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));
    head->next = NULL;
    addFront(head,2);
    addFront(head,1);
    addFront(head,7);
    addFront(head,8);
    removeFront(head);
    showAll(head);
    freeAll(head);
    return 0;
}

양방향 연결리스트

  • 양방향 연결리스트는 Head와 Tail를 모두 가진다는 특징이 있다.
  • 양방햔 연결리스트의 각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장하고 있다.
  • 단방향 연결리스트에 비해서 더 복잡하다.
    image.png

노드 삽입

  1. 삽입할 노드를 생성
    image.png

  2. 삽입할 노드의 앞쪽에 있는 노드가 삽입할 노드를 가르키도록 한다.
    image.png

  1. 삽입할 노드의 prev는 앞쪽의 노드를 가르키도록 한다.
    image.png
  1. 삽입할 노드의 뒤쪽에 있는 노드의 prev를 삽입할 노드를 가르키도록한다.
    image.png
  1. 삽입할 노도의 next를 뒤쪽의 노드를 가르키도록 한다.
    image.png
void insert(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
      node->data = data;
      Node* cur;
      cur = head->next;
      while(cur->data < data && cur != tail) {
        cur = cur->next;
    }
      Node* prev = cur->prev; //삽입할 노드의 앞에 있는 노드(삽입할 노드의 뒷부분 노드의 prev를 가르키므로)
      prev->next = node; // 앞 노드의 next에는 삽입할 노드
      node->prev = prev; // 삽입할 노드의 prev에는 앞노드
    cur->prev = node; // 뒷 노드의 prev에는 삽입할 노드
      node->next = cur; // 삽입할 노드의 next에는 뒷 노드
}

노드의 삭제

  1. 삭제할 노드를 입력받는다.
    image.png

  2. 삭제할 노드 앞노드의 next는 뒷노드를 가르키도록 한다.
    image.png

  3. 삭제할 노드의 뒷노드의 prev는 앞노드를 가르키도록 한다.
    image.png

  4. 삭제할 노드를 free 시킨다.
    image.png

void removeFront(){
  Node *node = head->next; //삭제할 노드주소값을 저장
  head->next = node->next; // 삭제할 노드의 앞부분의 next값을 삭제할 노드 뒷부분의 주소값을 바꾼다.
  Node *next = node->next; // 삭제할 노드의 뒷노드 주소값을 저장
  next->prev = head; // 뒷노드 의 prev값을 삭제할 노드의 앞노드 주소값으로 바꾼다.
  free(node); // 삭제할 노드의 연결이 끊겼으므로, free시켜서 메모리 할당 끝낸다.
}

양방향 연결리스트 출력

void show() {
  Node* cur = head->next; //현재 노드(제일 앞에 있는노드)를 가르키도록한다.
      while (cur != tail) { //현재노드가 tail(끝)까지 이동하도록 반복
      printf("%d ", cur->data); // 현재노드의 data 출력
      cur = cur->next; //cur이 다음 노드를 가르키도록해서 계속 한칸씩 이동
    }
}

양방향 연결리스트 전체코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int data;
    Node *prev;
    Node *next;
}Node;
Node *head, *tail;
void insert(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
      node->data = data;
      Node* cur;
      cur = head->next;
      while(cur->data < data && cur != tail) {
        cur = cur->next;
    }
      Node* prev = cur->prev; //삽입할 노드의 앞에 있는 노드(삽입할 노드의 뒷부분 노드의 prev를 가르키므로)
      prev->next = node; // 앞 노드의 next에는 삽입할 노드
      node->prev = prev; // 삽입할 노드의 prev에는 앞노드
    cur->prev = node; // 뒷 노드의 prev에는 삽입할 노드
      node->next = cur; // 삽입할 노드의 next에는 뒷 노드
}
void removeFront(){
  Node *node = head->next; //삭제할 노드주소값을 저장
  head->next = node->next; // 삭제할 노드의 앞부분의 next값을 삭제할 노드 뒷부분의 주소값을 바꾼다.
  Node *next = node->next; // 삭제할 노드의 뒷노드 주소값을 저장
  next->prev = head; // 뒷노드 의 prev값을 삭제할 노드의 앞노드 주소값으로 바꾼다.
  free(node); // 삭제할 노드의 연결이 끊겼으므로, free시켜서 메모리 할당 끝낸다.
}
void show() {
  Node* cur = head->next; //현재 노드(제일 앞에 있는노드)를 가르키도록한다.
      while (cur != tail) { //현재노드가 tail(끝)까지 이동하도록 반복
      printf("%d ", cur->data); // 현재노드의 data 출력
      cur = cur->next; //cur이 다음 노드를 가르키도록해서 계속 한칸씩 이동
    }
}
int main(void) {
  head = (Node*) malloc(sizeof(Node));
  tail = (Node*) malloc(sizeof(Node));
  head->next = tail;
  head->prev = head;
  tail->next = tail;
  tail->prev = head;
  insert(2);
  insert(1);
  insert(3);
  insert(9);
  insert(7);
  removeFront();
  show();
  system("pause");
  return 0;
}