LinkedList(3) - 양방향 연결리스트

양방향 연결리스트는 노드에 양쪽을 연결해서 previous(이전) next(다음)을 통해 이동할 수 있는 리스트의 형태이다.

이전 노드를 가리키는 변수의 추가로  before를 통해 이전 노드를 기억해야하는 과정을 뺄 수 있다.

출처:https://opentutorials.org/module/1335/8940

이전에 연결리스트 node에 previous를 가리킬 수 있는 변수만 추가해주면 된다.

 

-ADT

이전과 동일

단, 노드를 구현하는 부분 이전 노드를 가리키는 pre가 추가됨

typedef struct _node{

    Ldata data;

    struct _node* next;

    struct _node* pre;

}node;

 

-C 구현 (dummy기반 x)

 

>헤더파일 

#ifndef _DB_LINKED_LIST

#define _DB_LINKED_LIST

typedef int Ldata;

typedef struct _node{

    Ldata data;

    struct _node* next;

    struct _node* pre;

}node;

typedef struct db_linked_list{

    node* head;

    node* cur;

    int size;

}dblist;

typedef dblist List;

void Listinit(List* plist);

void Linsert(List* plist, Ldata data);

int Lfirst(List* plist,Ldata* data);

int LNext(List* plist,Ldata* data);

int Lprevious(List* plist,Ldata* data);

int Lsize(List* plist);

#endif

>소스파일 

#include<stdio.h>

#include<stdlib.h>

#include"DB_LinkedList.h"

void Listinit(List* plist){

    plist->head = NULL;

    plist->cur =NULL;

    plist->size =0;

}

void Linsert(List* plist, Ldata data){

    //맨 앞에 데이터 추가 양 끝은 null

    node* newnode = (node*)malloc(sizeof(node));

    newnode->data = data;

    newnode->next = plist->head; //처음에는 null, 다음부터는 있음

    if(plist->head != NULL){

        plist->head->pre = newnode;

    }

    newnode->pre = NULL;

    plist->head = newnode;

    (plist->size)++;

}

int Lfirst(List* plist,Ldata* data){

if(plist->head == NULL)

return 0;

plist->cur = plist->head;

*data =  plist->cur->data;

return 1;

}

int LNext(List* plist,Ldata* data){

    if(plist->cur->next == NULL)

    return 0;

    plist->cur = plist->cur->next;

    *data = plist->cur->data;

    return 1;

}

int Lprevious(List* plist,Ldata* data){

    if(plist->cur->pre == NULL) return 0;

     plist->cur = plist->cur->pre;

    *data = plist->cur->data;

    return 1;

}

int Lsize(List* plist){

    return plist->size;

}

새로운 데이터를 추가하는 과정만 조금 달라졌다.

 

>> 새로운 노드의 추가 (맨 앞에 데이터 추가)

1. newnode를 할당받고, 데이터 삽입 newnode의 next는 head를 가리킨다.

 

-1.1 head가 null이 아닐경우 head의 이전 노드를 newnode와 연결한다.

 

-1.2 head가 null일 경우 -> head에 이전 노드를 연결하지 않는다. head가 null이므로 다음 과정으로 head는 newnode가 되고, 양 끝은 null이 된다.

 

2.  newnode의 pre에 null을 할당한다. 이는 맨 앞에 노드가 추가되는 것이고, 맨 왼쪽의 pre와 맨 오른쪽 next를 null로 만들기 위함이다.

 

3. head에 newnode를 할당

 

- dummy기반 C구현 (head와 tail 추가)

 

헤더파일

#ifndef _DB_liked_dummy

#define _DB_liked_dummy

typedef int Ldata;

typedef struct _node{

    Ldata data;

    struct _node* next;

    struct _node* pre;

}node;

typedef struct db_linked_list_d{

    node* head;

    node* tail;

    node* cur;

    int size;

}dblist_d;

typedef dblist_d List;

void Listinit(List* plist);

void Linsert(List* plist, Ldata data);

int Lfirst(List* plist,Ldata* data);

int LNext(List* plist,Ldata* data);

int LPrivious(List* plist, Ldata* data);

Ldata LRemove(List* plist);

int Lsize(List* plist);

#endif

소스파일

#include<stdio.h>

#include<stdlib.h>

#include"DB_linked.h"

void Listinit(List* plist){

    plist->head = (node*)malloc(sizeof(node));

    plist->head->pre = NULL;

    plist->head->next = plist->tail;

   

    plist->tail = (node*)malloc(sizeof(node));

    plist->tail->pre=plist->head;

    plist->tail->next =NULL;

    plist->size =0;

     

}

void Linsert(List* plist, Ldata data){

    node* newnode = (node*)malloc(sizeof(node));

    newnode->data = data;

   

    newnode->next = plist->tail->pre->next; //초기에는 head->next인 tail

    newnode->pre = plist->tail->pre; //초기에는 tail->pre인 head

    plist->tail->pre->next = newnode; //초기에는 head->next가 newnode

    plist->tail->pre = newnode; //최근 이전노드를 newnode로 두기

   

   

    (plist->size)++;

}

int Lfirst(List* plist,Ldata* data){

    if(plist->head->next == plist->tail) return 0;

    plist->cur = plist->head->next;

    *data = plist->cur->data;

    return 1;

}

int LNext(List* plist,Ldata* data){

    if(plist->cur->next == plist->tail) return 0;

    plist->cur = plist->cur->next;

    *data =plist->cur->data;

    return 1;

}

int LPrivious(List* plist, Ldata* data){

    if(plist->cur->pre == plist->head) return 0;

    plist->cur = plist->cur->pre;

    *data =plist->cur->data;

    return 1;

}

Ldata LRemove(List* plist){

    node* Rnode = plist->cur;

    Ldata Rdata = Rnode->data;

   

    plist->cur->pre->next = plist->cur->next;

    plist->cur->next->pre = plist->cur->pre;

    plist->cur = plist->cur->pre; //이거 빼먹을뻔!

    free(Rnode);

    (plist->size) --;

    return Rdata;

}

int Lsize(List* plist){

    return plist->size;

}

 

> dummy ListInit

tail과 head를 추가하고 head->next = tail, tail->pre = head로 연결해둔다.

 

>dummy Insert

 

1. newnode에 data할당 

2. newnode->next = tail->pre->next 

    >초기에는 tail->pre(next) ->next이므로 tail을 의미

    > tail->pre가 newnode로 조정된 후에는 newnode->next의미 but 둘다 tail이긴하다.

3. newnode->pre = tail->pre 

   >초기에는 head의미 

   >tail->pre가 newnode로 조정된 후에는 이전 노드를 의미 

4. tail->pre->next = newnode

   >초기에는 head->next가 newnode가리킴 

   > tail->pre가 newnode로 조정되면, 이전노드의 next가 새 노드를 가리킴 

5. tail->pre = newnode 

 

>dummy remove 

 

삭제할 노드 위치 cur

cur->pre->next = cur->next (이전 노드의 next를 현재 노드의 next와 연결)

cur->next->pre = cur->pre (앞 노드의 pre를 이전 노드와 연결)

cur = cur->pre 현재 노드의 위치도 이전 노드에 옮겨둠 

->삭제할 노드의 연결 끊어지고 cur에 위치한 노드는 free로 메모리에서 제거하면 됨