/*
18.12.06
더블 링크드 리스트
노드1을 추가시에 피리스트가 가르키는 것을 노드1의 프리브를 가르킴
노드 2가 추가 되는 경우 동일하게 반복함
추가되는 노드는 항상 싱글 링크드 리스트에서 뒤쪽으로 추가됨
노드 내의 프리브라고 이름 지어진 이유이기도 함
싱글 링크드 리스트를 바탕으로 더블 링크드 리스트 설명
추가되는 노드1의 프리브, 넥스틑 먼저 지정해야 함
검색할 때 헤드에서 테일까지 혹은 테이엘서 헤드까지 검색할 수 있음
헤드에서 테일로 검색하는 경우
삭제
노드2가 가진 연결은 안지워도 됨
싱글 링크드 리스트도 피리스트 대신 더미 노드인 태일 노드를 미리 만들어 두고 사용하면 삭제시 좀 더 쉬움
해쉬와 싱글 링크드 리스트를 같이 사용하면 페이지 단어 검색에 대한 해결도 될 수 있음
*/
#include <iostream>
using namespace std;
int arr_idx = 0;
struct NODE {
int v;
NODE * prev; //for single linked list
NODE * next; //for double linked list
} a[20000];
NODE *myalloc(void)
{
return &a[arr_idx++];
}
NODE * pTail; //더블 링크드 리스트의 끝. (싱글 링크드 리스트의 pList의 역활)
NODE * pHead; //더블 링크드 리스트의 시작.
void print_node(void);
int main(void)
{
arr_idx = 0; //사용할 배열 초기화
pHead = myalloc(); //Head 노드를 미리 만들어둠.
pTail = myalloc(); //Tail 노드를 미리 만들어둠.
pTail->prev = pHead; //pHead <-> pTail 을 연결
pHead->next = pTail;
NODE *p;
// 노드 추가..
for (int i = 1; i < 10; i++)
{
p = myalloc();
p->v = i;
p->prev = pTail->prev; //기존 싱글 리스트 연결 방식과 동일(저장 위치만 pTail->prev 로 바뀜)
pTail->prev = p;
//next 연결.
p->next = p->prev->next; //이전노드가 가르키던걸 내가 가르키고.
p->prev->next = p; //이전 노드는 나를 가르키게 만듬.
}
print_node();
//HEAD 부터 검색해서 노드(5) 삭제
for (NODE * iter = pHead->next; iter != pTail; iter = iter->next) //HEAD 에서 모든 노드를 따라가면서..
{
if (iter->v == 5) //노드(5)를 찾으면
{
iter->prev->next = iter->next; //이전 노드의 다음(next)은 내가 가르키던 다음(next)을
iter->next->prev = iter->prev; //다음 노드의 이전(next)은 내가 가르키던 이전(prev)을
cout << "Delete 5 node ... " << endl << endl;
}
}
print_node();
//TAIL 부터 검색해서 노드(3) 삭제
for (NODE * iter = pTail->prev; iter != pHead; iter = iter->prev) //TAIL 에서 모든 노드를 따라가면서..
{
if (iter->v == 3) //노드(3)를 찾으면
{
iter->prev->next = iter->next; //이전 노드의 다음(next)은 내가 가르키던 다음(next)을
iter->next->prev = iter->prev; //다음 노드의 이전(next)은 내가 가르키던 이전(prev)을
cout << "Delete 3 node ... " << endl << endl;
}
}
print_node();
//TAIL 부터 검색해서 모든노드 삭제
for (NODE * iter = pTail->prev; iter != pHead; iter = iter->prev) //TAIL 에서 모든 노드를 따라가면서..
{
iter->prev->next = iter->next; //이전 노드의 다음(next)은 내가 가르키던 다음(next)을
iter->next->prev = iter->prev; //다음 노드의 이전(next)은 내가 가르키던 이전(prev)을
cout << "Delete node ... " << iter->v << endl << endl;
}
print_node();
//다시 노드 추가..
for (int i = 1; i < 10; i++)
{
p = myalloc();
p->v = i;
p->prev = pTail->prev; //기존 싱글 리스트 연결 방식과 동일(저장 위치만 pTail->prev 로 바뀜)
pTail->prev = p;
//next 연결.
p->next = p->prev->next; //이전노드가 가르키던걸 내가 가르키고.
p->prev->next = p; //이전 노드는 나를 가르키게 만듬.
}
print_node();
}
void print_node(void)
{
cout << "From head ~~ " << endl;
for (NODE * iter = pHead->next; iter != pTail; iter = iter->next)
cout << iter->v << " ";
cout << endl;
cout << "From tail ~~ " << endl;
for (NODE * iter = pTail->prev; iter != pHead; iter = iter->prev)
cout << iter->v << " ";
cout << endl << endl;
}
댓글