Double Linked List, 더블링크드리스트

소개글

Double Linked List, 더블링크드리스트 에 대한 보고서 자료입니다.

목차

● 프로그램 소개
● 프로그램 구현 소스
● 결과화면
● 프로그램을 하면서 느낀점

본문내용

digit = D;
N->nextfwd = NULL;
N->nextbwd = NULL;
if (B->front == NULL)
B->front = B->back = N;
else
//새로운 자릿수를 더한다
{
//전 front 에 포인터 설정
B->front->nextbwd = N;
// 자릿수를 위한 포인터 설정
N->nextfwd = B->front;
B->front = N;
}
}
void addDigitBack(BigInt * B, int D)
{
iNodeptr N = (iNodeptr)malloc (sizeof(Node));
N->digit = D;
N->nextfwd = NULL;
N->nextbwd = NULL;
if (B->front == NULL)
B->front = B->back = N;
else
//새로운 자릿수를 더한다
{
//전 front 에 포인터 설정
B->back->nextfwd = N;
// 자릿ㅁ수를 위한 포인터 설정
N->nextbwd = B->back;
B->back = N;
}
}
void clearBigInt(BigInt * B)
{
iNodeptr Bptr;
B->back = NULL;
while ((Bptr = B->front) != NULL)
{
B->front = Bptr->nextfwd;
free(Bptr);
}
}
● 결과화면
거대정수 범위를 60~70 자리 내외로 잡고 계산을 시도
중간 1/2 지점이 덧셈 부분이다
마지막은 곱셈의 출력이다
● 프로그램을 하면서 느낀점
단순 연결리스트와 함께 가장 많이 사용되는 이중 연결 리스트(double linked list)는 한 방향인 단순 연결리스트와 다르게 노드의 선행 노드를 가리키는 front, 데이터필드, back의 세 개 영역으로 각 노드를 구분하여 양방향으로 특정 노드를 검색할 수 있도록 한 구조이다. 전에 했던 숙제와 비슷하게 내용은 단순연결리스트랑 크게 다른 것이 없지만 앞의 노드를 가리킬 수 있는 것이 추가가 되었다. 그래서 이중 연결리스트는 다음의 노드를 가리키는 링크와 전의 노드를 가리키는 링크 두 가지를 가져서 바로 전의 노드에도 접근할 수 있다는 것이 가장 큰 장점이라는 것을 실감했다. 코딩 하면서 느낀 것은 단순 연결리스트보다 접근하는 점이 유연했고 역시 앞의 노드도 메모리 할당을 하기 때문에 그에 수반되는 메모리를 차지하므로 공간 소비는 더 크다.
이중연결리스트의 노드 구성은 다음과 같다.
front(f) : 앞 노드를 가리키는 포인터
back(b) : 뒤 노드를 가리키는 포인터
┌─────┐
│ Data │
├──┬──┤
│ f b │
└──┴──┘
초기화된 모습
┌─────┐ ┌─────┐
┌→ │ Data │←┐┌─→ │ Data │ ←┐
│ ├──┬──┤ └┼─┐ ├──┬──┤ │
│ │ f b │ │ │ │ f b │ │
│ └──┴──┘ │ │ └──┴──┘ │
└──┘ └───┘ └──┘ └──┘
head tail
┌─┐→ ┌─┐→ ┌─┐→ ┌─┐→ ┌─┐
└─┘← └─┘← └─┘← └─┘← └─┘

키워드

더블링크드리스트,   Double Linked List,   자료구조,   프로그램