[C/C++ 자료구조] 양방향 연결리스트와 C++ STL <list>

저번 시간은 연결리스트와 단방향 연결리스트에 대해 알아보고 구현해보았습니다.

 

오늘은 양방향 연결리스트와 C++ STL에 들어있는 함수들을 알아보고자 합니다.

 

List by Виталий Плут from the Noun Project

#양방향 연결리스트

 

양방향연결리스트의 특징은 head와 tail 노드를 사용하여 이 리스트를 관리하는 특징을 가지고 있습니다.

 

또한 한 노드가 전 노드 혹은 후 노드와 연결되어 있다는 점이 특징입니다.

 

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

typedef struct Node {
    int data;
    struct Node *prev;
    struct 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->next = node;
    node->prev = prev;
    cur->prev = node;
    node->next = cur;
}

void show(){
    Node* cur = head->next;
    while(cur!=tail){
        printf("%d ", cur->data);
        cur = cur->next;
    }
}
void pop_front(){
    Node* node = head->next;
    head->next = node->next;
    Node* next = node->next;
    next->prev = head;
    free(node);
}
void pop_back(){
    Node* node = tail->prev;
    tail->prev = node->prev;
    Node* prev = node->prev;
    prev->next = tail;
    free(node);
}
void push_back(int data){
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->prev = tail->prev;
    tail->prev->next = node;
    tail->prev = node;
    node->next = tail;
}
void push_front(int data){
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = head->next;
    head->next->prev = node;
    head->next = node;
    node->prev = head;
    
}
void clear(){
    Node*cur = head->next;
    while(cur!=tail){
        Node* node = cur;
        free(node);
        cur=cur->next;
    }
    free(head);
    free(tail);
}
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(1);
    insert(2);
    insert(3);
    push_front(4);
    pop_front();
    pop_back();
    push_back(5);
    show();
    //clear(); clear()함수를 사용하면 결과창에 아무것도 출력되지 않고 모든 Node가 free가 됩니다.
    
    return 0;
}

insert, show, pop_front, pop_back, push_back, push_front 그리고 clear를 구현해 보았는데요. 

 

이는 바로 뒤에 알아볼 C++ STL의 list안에 있는 함수를 C로 구현해본 것입니다.

 

insert는 숫자를 삽입할 때 오름차순으로 삽입하는 함수라 1 2 3이, 그리고 push_front(4)로 인해 4 1 2 3, pop_front()로 인해 다시 1 2 3 , pop_back()을 통해 1 2 , 마지막으로 push_back(5)에 의해 1 2 5가 결과적으로 각 노드에 하나씩 저장되어 있으며 show()를 통해 불러냅니다.

 

#C++ STL<list>

 

C++를 사용하게 되면 위와 같이 처음부터 구현할 필요 없이 list를 지원하여 위와 같은 함수를 쉽게 사용할 수 있게 됩니다.

 

#include<list>를 include하여 사용할 수 있습니다. 그렇다면 어떤 함수들이 있는지 간략하게 알아보고자 합니다.

 

 

• begin : 처음 데이터 호출
• end : 마지막 데이터 호출
• empty : list가 비어있을 시 1을 반환
• size : listdml zmrlfmf qksghks
• push_front : 맨 앞의 데이터 삽입
• pop_front : 맨 앞의 데이터 추출
• insert : 데이터를 원하는 위치에 삽입 ( 위의 insert는 순서대로 삽입이지만 STL에서는 원하는 위치에 삽입가능)
• erase : 원하는 데이터를 찾아 지움
• swap : 특정 위치의 데이터의 위치를 서로 바꿈
• sort : 정렬
• reverse : 역순으로 정렬

이처러 list를 사용할 수 있고 더 많은 함수가 #include<list> 안에 있으니 오른쪽의 링크를 참조하세요. http://www.cplusplus.com/reference/list/list/

list - C++ Reference

 

또한 이번 강의도 안경잡이 개발자 나동빈 강사님의 insert, show, pop_front 함수를 참고하여 다른 함수를 더하고 재가공하여 작성하였음을 알립니다. https://blog.naver.com/ndb796

안경잡이개발자 : 네이버 블로그