양방향 연결 리스트(doubly linked list) 또는 이중 연결리스트 라고도 불리는 이 자료구조는 그 이름이 의미하듯 노드가 양쪽 방향으로 연결된 구조의 리스트이다. 즉 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다.
양방향 연결리스트의 구조
head->2-><-4-><-6-><-8->NULL
위에서 보이듯이 하나의 노드가 자신의 왼쪽 노드과 오른쪽 노드를 동시에 가리키는 구조가 양방향 연결 리스트이다.
때문에 양방향 연결리스트의 노드를 표현하는 구조체는 다음과 같이 정의된다.
typedef struct _node
{
Data data; //typedef int Data
struct _node *next ; //오른쪽 노드를 가리키는 포인터 변수
struct _node *prev; //왼쪽 노드를 가리키는 포인터 변수
}Node;
그리고 더미노드가 추가된 양방향 연결리스트도 존재하는데, 더미 노드의 이점은 단순연결리스트에서 보인바와 같다.
또한 양방향 연결리스트이면서 원형 연결 리시트의 구조를 동시에 지니는 리스트도 존재한다.
하지만 지금 보인 세 가지 모데링 양방향 연결 리스트의 전부가 아니다. 이들 모두 꼬리를 가리키는 포인터 변수 tail이 없었으나 필요하면 추가할 수 있고, 또 두번째로 소개한 양방향 연결리스트의 경우, 더미 노드가 앞에만 존재하는 형태이지만, 필요에 따라서 뒤에도 더미 노드를 둘 수 있다.
일반적인 선입견은 양방향 연결리스트가 단방향 연결리스트보다 그 구조가 복잡하고 구현이 쉽지 않다는 것이다.
하지만 이는 그림상에서 느껴지는 복잡함 때문에 발생한 오해이다 .실제로 코드를 비교해보면 상대적으로 더 복잡하지 않음을 알수있다. 양쪽 방향으로 이동할 수 있기 때문에 단방향 연결 리스트에서 어렵게 구현 했던 것이 쉽게 구현되기 도한다. 때문에 오히려 단순하게 느껴지는 측면도 있다.
양방향 연결리스트와 앞서 보인 원형연결리스트의 몇몇 함수를 비교해보자 .
int LNext(List *plist, Data *pdata) //CLinkedList.c의 LNext 함수
{
if(plist->tail==NULL)
return FALSE;
plist->before = plist->cur;
plist->cur= plist->cur->next;
*pdata= plist->cur->data;
return TRUE;
}
다음은 잠시 후에 소개할 양방향 연결리스트의 LNext함수이다.
int LNext(List *plist, Data *pdata) //양방향 연결 리스트의 LNext함수
{
if(plist->cur->next ==NULL)
return FALSE;
plist->cur = plist->cur->next;
*pdata = plist->cur ->data;
return TRUE;
}
위에 두 LNext함수는 매우 유사하다 .LNext 함수가 하는 일의 순서나 내용이 리스트의 구조에 따라서 크게 달라지지 않기 때문이다. 그럼에도 불구하고 '원형 연결리스트'의 LNext함수는 '양방향 연결 리스트'의 LNext함수보다 한 가지 일을 더한다. 그리고 그 한가지 일에 해당하는 문장은 다음과 같다.
plist->before = plist->cur;
포인터 변수 before의 용도를 기억하는가? 이는 리스트가 한쪽 방향으로만 조회가 가능하기 때문에 유지해야 하는, 삭제의 과정을 위해 유지하는 멤버이다. 하지만 양방향 연결리스트는 양방향으로 얼마든지 조회가 가능하다. 따라서 포인터 변수 before이 불필요하고, before를 유지하기 위해 곳곳에 존재하는 문장들도 불필요하다.
이렇듯 양방향으로 노드를 연결하는 것에는 큰 이점이 있다. 물론 노드를 양방향으로 연결하기 위해서는 몇몇 문장이 추가된다. 하지만 그래 봤자 노드의 삽입 및 삭제 과정에서 한두 문장이 더 추가되는 정도이니, 떄문에 코드가 더 복잡해진다는 생각을 버리는 것이 옳다.
양방향 연결 리스트의 구현을 위한 헤더파일 정의
아까 소개한 양방향 연결리스트의 첫번째 모델이다.
LRemove 함수를 제외시키는 대신에 다음 함수를 추가할 것이다.
int LPrevious(List *plist, Data *pdata); //LNext 함수의 반대방향으로 노드 참조
이는 양방향 연결리스트가 아니면 구현하기 힘든 함수이다. 이 함수는 LFirst 또는 LNext 함수가 호출된 이후에 어디서든 호출이 가능하며, LNext함수가 오른쪽 노드로 이동해서 그 노드의 데이터를 참조하는 함수라면, 이 함수는 그와 반대인 왼쪽노드로 이동해서 그 노드의 데이터를 참조하는 함수라고 할 수 있다.
#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef struct _node
{
Data data;
struct _node *next;
struct _node *prev;
}Node;
typedef struct _DLinkedList
{
Node *head;
Node *cur;
int numOfData;
}DBLinkedList;
typedef DBLinkdList List;
void ListInit(List *plist);
void LInsert(List *plist, Data data);
int LFirst(List *plist, Data *pdata);
int LNext(List *plist, Data *pdata);
int LPrevious(LIst *plist, Data *pdata);
int LCount(List *plist);
#endif
양방향 연결 리스트의 LInsert함수도 리스트의 머리에 새 노드를 추가하는 방식으로 구현할 것이다.
양방향 연결 리스트의 구현 1 : 리스트의 초기화와 노드의 삽입
양방향 연결 리스트이 초기화를 담당하는 ListInit 함수의 정의를 위해서 다음 구조체를 보자.
typedef struct _dbLinkedList
{
Node *head;
Node *cur;
int numOfData;
}DBLinkedList;
위의 구조체에서 주목할 것은, 데이터의 조회를 목저긍로 선언된 멤버가 cur 하나라는 사실이다. 즉 단순 연결리스트에는 있었던 before가 존재하지 않는다. 따라서 ListInit 함수는 다음과 같이 정의가 된다.
void ListInit(List *plist)
{
plist->head =NULL;
plist->numOfData =0;
}
조회에 사용되는 멤버 cur은 LFirst함수가 호출됨과 동시에 초기화되니, 위의 함수에서는 별도로 초기화 할 필요가 없다. 그럼 이어서 LInsert 함수를 구현해보자.
새로운 노드는 리스트의 머리에 추가가 되니, 데이터의 저장돠 관련해서 다음 두 가지 상황을 고려하면된다.
head->4
4의 next와 prev는 NULL
두번쨰 노드 삽입
head ->2-><-4
2의 prev와 4의 next는 NULL
위 과정에서 보이듯이 첫 번째 노드를 추가하는 과정과 두 번째 이후의 노드를 추가하는 과정이 다르기 때문에 이 둘을 나누어서 생각해야 한다. 그럼 첫 번째 노드의 추가 과정을 코드로 옮겨보자
void LInsert(List *plist, Data data) //첫번째 노드의 추가 과정만 담음
{
Node *newNode= (Node *)malloc(sizeof(Node));
newNode->data = data;
//아래 문장에서 plist->head는 NULL이다
newNode->next = plist->head; //새 노드의 next를 NULL로 초기화
newNode->prev= NULL; //새 노드의 prev를 NULL로 초기화
plist->head= newNode; //포인터 변수 head가 새 노드를 가리키게 함
(plist->numOfData)++;
}
연결 리스트가 텅빈 상황에서, 연결리스트의 포인터 변수 head에는 NULL이 저장되어 있음을 기억하고 위의 코드를 이해해야 한다. 결국 위의 함수에서 하는 일은 새노드와 next와 prev를 NULL로 초기화하고, 이 새 노드를 head가 가리키게 하는 것이 전부이다.
이번에는 위의 함수에 두 번째 이후 노드를 추가하는 과정을 더해서 함수를 완성할 차례이다. 이를 위해서 먼저 두 번째 노드의 추가 과정을 정리해보겠다.
첫번째 노드가 추가된 상황에서, 두 번째 노드를 추가하기 위해서 먼재 해야할 일은 다음과 같다.
"새 노드를 생성하고, 이 새노드와 head가 가리키는 노드가 서로를 가리키게 한다."
head->4-><-2
newNode= 2
그리고 이 과정은 다음 두 문장을 통해 완성이 된다.
newNode ->next = plist->head; //새노드가 기존 노드를 가리키게 한다.
plist->head->prev= newNode; //기존노드가 새 노드를 가리키게한다.
이제 head가 새 노드를 가리키게 하고, 새 노드의 prev에 NULL을 채워서 다음의 형태가 되게 하면 두 번째 노드의 추가도 끝이 난다.
head->2-><-4->NULL
2의 prev NULL
그리고 다음 문장을 통해 위의 과정이 완성된다.
newNode->prev= NULL; //새 노드의 prev에 NULL 저장
plist->head =newNode; //포인터 변수 head가 새노드를 가리키게 한다.
이로써 새로운 노드의 추가에 필요한 코드를 부분적으로나마 모두 작성하였다.
그러니 이제 이를 하나로 묶기만 하면 된다. 그러면 다음의 함수가 완성이 된다.
void LInsert(List *plist, Data data)
{
Node *newNode= (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next= plist->head;
if(plist->head !=NULL) // 두번째 이후의 노드를 추가할 때만 실행
plist->head->prev =newNode;
newNode->prev =NULL;
plist->head= newNode;
(plist->numOfData)++;
}
이로써 양방향 연결리스트의 LInsert 함수를 완성하였다.
양방향 연결 리스트의 구현 2 :데이터 조회
이번에 구현할 데이터의 조회와 관련있는 다음 세 함수의 구현은 어려울 것이 없다. 특히 LFirst와 LNext 함수는 단반향 연결리스트의 경우와 사실상 차이가 없다.
int LFirst(List *plist, Data *pdata); //첫번째 노드의 데이터 조회
int LNext(List *plist, Data *pdata); //두번째 이후의 노드 데이터 조회
int LPrevious(List *plist, Data *pdata); //LNext의 반대 방향으로 데이터 조회
이 중에서 LFirst 함수와 LNext 함수는 단방향 연결 리스트의 경우보다 오히려 간단히 구현된다. 단방향 연결리스트에는 있었던 구조체 멤버 before가 없어졌기 때문이다.
int LFirst(List *plist, Data *pdata)
{
if(plist->head ==NULL)
return FALSE;
plist- >cur= plist->head; //cur이 첫번째 노드를 가리키게 함
*pdata =plist->cur->data; //cur이 가리키는 노드의 데이터 반환
return TRUE;
}
int LNext(List *plist, Data *pdata)
{
if(plist->cur->next ==NULL)
return FALSE;
plist->cur = plist->cur->next; //cur을 오른쪽으로 이동
*pdata = plist->cur->data; //cur이 가리키는 노드의 데이터를 반환
return TRUE;
}
int LPrevious(List *plist, Data *pdata)
{
if(plist->cur->prev ==NULL)
return FALSE;
plist->cur= plist->cur->prev; //cur을 왼쪽으로 이동
*pdata = plist->cur->data; //cur이 가리키는 노드의 데이터 반환
return TRUE;
}
위의 LPrevious 함수는 LNext 함수의 반대 방향으로 데이터를 조회하기 때문에 구조체 Node의 멤버 next가 아닌 prev를 사용해서 cur을 이동시켰다. 그리고 그것이 LNext 함수와의 유일한 차이점이다.
양방형 연결리스트의 구현을 하나로 묶어보겠다.
//DBLinkedList.h
#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__
#define TURE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next;
struct _node * prev;
}Node;
typedef struct _DLinkedList
{
Node *head;
Node *cur;
int numOfData;
}DBLinkedList;
typedef DBLinkedList List;
void ListInit(List * plist);
void LInsert(List *plist, Data data);
int LFirst(List *plist, Data *pdata);
int LNext(list *plist, Data *pdata);
int LRevious(List *plist, Data *pdata);
int LCount(List *plist);
#endif
//DBLinkedList.c
#include <stdio.h>
#include <stdlib.h>
#include "DBLinkedList.h"
void ListInit(List *plist) //리스트의 초기화
{
plist->head= NULL;
plist->numOfData =0;
}
void LInsert(List *plist, Data data) //리스트의 생성
{
Node * newNode = (Node*)malloc(sizeof(Node)); //노드 생성
newNode->data= data; //데이터 입력
newNode->next= plist->head; //newNode의 next를 head값으로
if(plist->head !=NULL); //두번째 이후 노드부터
plist->head->prev= newNode; //헤드의 왼쪽에 newNode;
newNode->prev=NULL; //newNode의 이전노드를 NULL로 초기화
plist->head= newNode; //head를 newNode로 변경
(plist->numOfData)++;
}
int LFirst(List *plist, Data *pdata)
{
if(plist->head ==NULL); //저장된 데이터가 없다면
return FALSE;
plist->cur= plist->head; //첫번째 데이터를 가리킴
*pdata= plist->cur->data; //첫번째 데이터의 값 저장
return TRUE; //첫번째 데이터 반환
}
int LNext(List *plist, Data *pdata)
{
if(plist->head ==NULL); //저장된 데이터가 없다면
return FALSE;
plist->cur= plist->cur->next; //cur을 다음 노드로 이동
*pdata= plist->cur->data; //데이터 저장
return TRUE;
}
int LPrevious(List *plist, Data *pdata)
{
if(plist->cur->prev==NULL)
return FALSE;
plist->cur=plist->cur->prev;
*pdata = plist->cur->data;
return TRUE;
}
int LCount(List *plist)
{
return plist->numOfData;
}
//DBLinkedListMain.c
#include <stdio.h>
#include "DBLinkedList.h"
int main()
{
//양방향 연결 리스트의 생성 및 초기화
List list;
int data;
ListInit(&list);
//8개의 데이터 저장
LInsert(&list, 1);LInsert(&list, 2);
LInsert(&list, 3);LInsert(&list, 4);
LInsert(&list, 5);LInsert(&list, 6);
LInsert(&list, 7);LInsert(&list, 8
//저장된 데이터의 조회
if(LFirst(&list, &data))
{
printf("%d ", data);
//오른쪽 노드로 이동하며 데이터 조회
while(LNext(&list, &data))
printf("%d ", data);
//왼쪽 노드로 이동하며 데이터 조회
while(LPrevious(&list, &data))
printf("%d ", data);
printf("\n\n");
}
return 0;
}
=================================실행 결과===================
8 7 6 5 4 3 2 1 2 3 4 5 6 7 8