[자료구조] 이중 연결리스트 (double linked list) 요약

단일 연결리스트는 하나의 노드에 next가 다음노드의 주소를 가리키며 쭉 연결되어있는 리스트를

단일 연결리스트라고 하였습니다.

그렇다면 이중연결리스트는?

이중연결리스트는 말 그대로 모든 노드가 이전노드와 다음노드 에 대한 주소를 모두 저장학고있는 리스트를 의미합니다.

이중연결리스트는 단일연결리스트보다 약간의 메모리를 더 차지하긴 하겠지만 양방향 이동이 가능하기 때문에 리스트 삽입,삭제,추가 등을 할때 더욱 편리합니다. 

 

아래 사진을통해 간단하게 정리되어있길래 가져와봤습니다!  참고)movahws.tistory.com/113

 

 

 

 

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

struct NODE //구조체 선언
{
    struct NODE* llink;
    int data;
    struct NODE* rlink;
};
struct NODE* head;
struct NODE* tail;

//노드 생성 함수
struct NODE* makenode(int value){
    struct NODE *node = (struct NODE*)malloc(sizeof(struct NODE));
    node->llink = NULL;
    node->data = value;
    node->rlink = NULL;
    return node;
}

//출력 함수
void print(){
    struct NODE *p;
    p = head;
    while(p->rlink != tail){
        printf("%d-->",p->data);
        p = p->rlink;
    }
    printf("%d",p->data);
}

//초기화 함수
void init(){
    head = (struct NODE*)malloc(sizeof(struct NODE));
    tail = (struct NODE*)malloc(sizeof(struct NODE));
    head->data = 0;
    tail->data = 0;

    head->rlink = tail;
    head->llink = head;
    tail->rlink = tail;
    tail->llink = head;
}

//뒤로부터 노드 추가하는 함수
void push_back(int value){ 
    struct NODE* newnode = makenode(value);
    struct NODE* p;
    p = tail;
    p->llink->rlink = newnode;
    newnode->llink = p->llink;
    p->llink = newnode;
    newnode->rlink = p;
}

//main함수
int main(){
    init(); //head와 tail 초기화 (data = 0)
    push_back(10); //10 추가
    push_back(30); //30 추가
    push_back(50); //50 추가
    print();  //출력
    return 0;
}