doubly linked list는 말 그대로 이전 single linked list와는 다르게 한 구조체 내부에 2개의 구조체 포인터가 있는 것이다.

헤더 분석

#ifndef _DOUBLYLIST_
#define _DOUBLYLIST_

typedef struct DoublyListNodeType
{
	int data;
	struct DoublyListNodeType* pLLink;
	struct DoublyListNodeType* pRLink;
} DoublyListNode;

typedef struct DoublyListType
{
	int	currentElementCount;		// ���� ����� ������ ����
	DoublyListNode	headerNode;		// ��� ���(Header Node)
} DoublyList;

DoublyList* createDoublyList();
void deleteDoublyList(DoublyList* pList);
int addDLElement(DoublyList* pList, int position, DoublyListNode element);
int removeDLElement(DoublyList* pList, int position);
void clearDoublyList(DoublyList* pList);
int getDoublyListLength(DoublyList* pList);
DoublyListNode* getDLElement(DoublyList* pList, int position);
void displayDoublyList(DoublyList* pList);

#endif

#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_

#define TRUE		1
#define FALSE		0

#endif

위의 DoublyList는 이전 LInkedList와 다른 점이 없지만, DoublyListNode는 pLLink, pRLink 이 두 개의 구조체 포인터를 멤버 변수로 갖고 있는 것을 확인할 수 있다.

아래와 같이 한 구조체가 2개의 구조체 포인터와 데이터를 가진다.

createDoublyList 함수 구현

DoublyList* createDoublyList()
{
  	DoublyList* pList = NULL;
  	pList = (DoublyList*)malloc(sizeof(DoublyList));
  	if (pList == NULL)
    {
        printf("malloc failure\\n");
        return (NULL);
    }
  	memset(pList, 0, sizeof(DoublyList));
  	pList->headerNode.pRLink = &(pList->headerNode);//헤더노드의 pLLink,pRLink값을 모두 헤더노드 주소로
  	pList->headerNode.pLLink = &(pList->headerNode);
  	return (pList);
}

함수 기능 : DoublyList 타입 변수를 동적 할당하고 이 주소값을 리턴하는 함수.

이전 LinkedList버전과는 다르게 이번에는 pList의 headerNode의 pRLink를 헤더노드의 주소로, pList→headerNode.pLLink 또한 헤더노드의 주소로 한 것이 다르다. 위 그림대로 구현하면 된다.

addDLElement 함수 구현

int addDLElement(DoublyList* pList, int position, DoublyListNode element)
{
  	DoublyListNode* pNode = NULL;
	DoublyListNode* nextNode = NULL;
  
  	if (pList != NULL)
    {
      if (position >= 0 && position <= pList->currentElementCount)
      {
      	nextNode = (DoublyListNode*)malloc(sizeof(DoublyListNode));
        if (nextNode != NULL)
        {
          pNode = &(pList->headerNode);
          
          *nextNode = element;
          nextNode->pLLink = NULL;
          nextNode->pRLink = NULL;
          if (pList->currentElementCount == 0)//첫번째 case. node가 아무것도 없고 0번째에 노드 추가
          {
            pNode->pLLink = nextNode;
            pNode->pRLink = nextNode;
            nextNode->pLLink = pNode;
            nextNode->pRLink = pNode;
          }
          else//2번째 case. node가 1개 이상인 상태에서 position에 노드 추가
          {
            for(int i = 0; i < position; i++)
            {
              pNode = pNode->pRLink;
            }
            nextNode->pLLink = pNode;
            nextNode->pRLink = pNode->pRLink;
            pNode->pRLink = nextNode;
          }
          (pList->currentElementCount)++;
					return (TRUE);
        }
      }
    }
  return (FALSE);
}

DoublyList에서 노드를 추가하는 함수가 바로 이 함수이다.

이 함수에서 노드를 추가하는 case는 총 2가지가 있다. 노드가 1개 이상일 때, 맨 마지막 노드를 지우는 경우까지 총 3가지가 있다고 생각할 수 있으나 이 경우는 2번 case에 속한다. 따라서 2가지 경우이다.

1 ) 리스트에 노드가 아무것도 없고 0번째에 노드를 추가하는 경우

pNode가 헤더 노드를 가리키게 하고, nextNode에 추가할 노드를 집어넣자.

pNode의 pLLink와 pRLink 모두 nextNode의 주소이다. 또, nextNode의 pLLink와 pRLink 모두 pNode의 주소이다.

2 ) 리스트에 노드가 1개 이상 있을 때 추가하는 경우