열혈 자료구조 - 5-2. 양방향 연결 리스트(2)

양방향 연결 리스트의 구현

- 양방향 연결 리스트의 구조체

    -> 노드에 양방향을 가르킬 수 있는 노드 2개를 선언

typedef struct _node
{
	Data data;
	struct _node * next;
	struct _node * prev;
} Node;

typedef struct _dbLinkedList
{
	Node * head;
	Node * cur;
	int numOfData;
} DBLinkedList;

- 노드 추가

   -> HEAD에 추가

void LInsert(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head;
  	// 첫번째 노드는 next가 NULL이 되어야 하고 그 이후는 next가 HEAD가 되어야 함
   	// 처음에 head는 NULL이기 때문에 이렇게 코드를 넣으면 두 경우 모두를 만족시킬 수 있음
    
	if(plist->head != NULL)
		plist->head->prev = newNode;		// 새 노드와 head를 연결

	newNode->prev = NULL;
	plist->head = newNode;

	(plist->numOfData)++;
}

- 조회

    -> 이전처럼 First는 cur는 헤드를 그 이후의 조회인 Next는 cur의 next가 cur이 됨

    -> 만약 이전으로 돌아가는 조회 ADT를 추가한다면 cur은 cur의 prev를 받으면 됨

int LPrevious(List * plist, Data * pdata)
{
	if(plist->cur->prev == NULL)
		return FALSE;

	plist->cur = plist->cur->prev;
	*pdata = plist->cur->data;

	return TRUE;
}

- 삭제

    -> 노드를 삭제 후 그 노드 양쪽의 노드를 prev와 next를 연결

Data LRemove(List * plist)
{
	Node * rpos = plist->cur;
	Data remv = rpos->data;

	if ( plist->cur != plist->head )
    {
		plist->cur->prev->next = plist->cur->next;
    	if ( plist->cur->next != NULL)	// cur에 다음 노드가 있는 경우
			plist->cur->next->prev = plist->cur->prev;

		plist->cur = plist->cur->prev;    // cur의 위치를 재조정
	} // cur이 head가 아닌 경우
    
	free(rpos);
	(plist->numOfData)--;
	return remv;
}