DLL(Doubly Linked List)

개념

한 개의 링크로 노드들을 이은 SLL과 달리, 앞과 뒤의 노드를 잇는 2개의 링크를 갖는 자료구조이다.

따라서 이전 노드로 이동하기는 힘든 SLL의 단점을 DLL에서 보완할 수 있다.

 

구현(C/C++)

- 구조체 선언

typedef struct node
{
    int i;
    struct node*next;
    struct node*prev;
}node;

- DLL에 노드 추가

void add(int a)
{
    node *newnode = (node*)malloc(sizeof(node));
    newnode->i=a;
    newnode->next=newnode->prev=0;

    if(head==0)
    {
        head=newnode;
        return;
    }

    node*last = head;
    while(last->next!=0)
    {
        last=last->next;
    }
    last->next=newnode;
    newnode->prev=last;
    return;
}

- DLL에 노드 삽입

void insertToDLL(int where, int what)
{
    struct node *cur = head;
    struct node *newnode = 0;
    
    while(1) //삽입할 위치 찾기
    {
    	if(cur==0) return;
        if(cur->i != where) cur=cur->next;
        else break;
    }
    
    newnode = (node*)malloc(sizeof(node));
    newnode->next = newnode->prev=0;
    
    newnode->next = cur->next;
    newnode->prev = cur;
    cur->next = newnode;
    if(newnode->next!=0)
    {
    	newnode->next->prev = newnode;
    }
}

- DLL에서 노드 삭제

void delFromDLL(int which)
{
    struct node *cur = head;
    while(1) //지울 노드 찾기
    {
    	if(cur==0) return;
        if(cur->i!=which) cur=cur->next;
        else break;
    }
    //cur이 지울 노드를 가리키므로 삭제
    if(cur==head)
    {
    	head=head->next;
        if(head!=0)
        {
        	head->prev=0;
        }
        free(cur);
    }
    else
    {
    	cur->prev->next = cur->next;
        if(cur->next!=0)
        {
        	cur->next->prev = cur->prev;
        }
        free(cur);
    }
}

- DLL의 데이터 출력

void printDLL() //SLL과 출력과정은 동일
{
    node *cur = head;
    while(cur!=0)
    {
    	cout<<cur->i<<endl;
        cur=cur->next;
    }
}