linked list - 이중(doubly) 연결 리스트(c++)

양방향으로 연결돼있는 linked list이다.

현 노드에서 이전 노드와 앞의 노드로 갈 수 있다.

+ singly linked list는 각 노드가 다음 노드만 가리킨다.

+ circular linked list는 각 노드가 다음 노드만 가리키는데, 마지막 노드가 처음 노드를 가리키고 있다.

 

프로그래머스 풀이 시 doubly linked list를 만들 일이 있어서 doubly로 쓰게 되었으나, Node 만드는 법만 알면 다른것도 쉽게 만들 수 있다.

 

Node struture을 만들어준다. 간단한거라서 struture로, 복잡한건 class로 만들자.

만드는 법을 까먹었다면(내가 까먹음) 아래를 참고해주자.

https://docs.microsoft.com/ko-kr/cpp/cpp/initializing-classes-and-structs-without-constructors-cpp?view=msvc-170 

클래스, 구조체 및 공용 구조체에 대한 중괄호 초기화

 

각 노드는 data와 가리키고 있는 전과 후의 노드를 가지고 있다.

또한 초기화를 쉽게 하기 위해서, default값은 0, NULL, NULL로 설정해주고, 초반에 값을 입력 받을 수 있도록 하였다.

 

struct Node{
    Node(int data=0, Node* prev=NULL, Node* next=NULL) :
        data{data}, prev{prev}, next{next}{}

    int data;
    Node* prev;
    Node* next;
};

 

잘 작동하는지 알아보기 위해서 print_linked_list라는 출력 함수를 만들어주었고,

main에서 값을 random으로 넣고 확인한 뒤 출력해보았다.

void print_linked_list(Node* linked_list){
    while(linked_list != NULL){
        cout<<linked_list->data;
        if(linked_list->next !=NULL) cout<<"-";
        linked_list = linked_list->next;
    }
    cout<<endl;
}

int main() {
    Node* linked_list = new Node();
    Node* start_list = linked_list;
    srand(time(NULL));

    for(int i=0; i<10; i++){
        int x = rand()%100;
        cout<<x<<" ";
        linked_list->next = new Node(x, linked_list);
        linked_list = linked_list->next;
    }
    cout<<endl;

    print_linked_list(start_list);

    return 0;
}​