list 구현

소개

 

리스트는 노드기반 컨테이너 입니다. 때문에 노드를 설계하는 것이 중요합니다.

 

단일 list나 이중 list나 만드는 과정은 똑같으므로 단일 list를 보여드리겠습니다.

 

이중 list는 Node에 이전 노드를 가리키는 포인터를 추가하고, 단일과 똑같이 연결을 끊어주고 이어주면 됩니다.

 

핵심적인 예외처리만 설명하고, 일부 예외처리는 생략하겠습니다. 궁금하시면 댓글 남겨주세요

 

구현

 

Node

 

 

tData    : 데이터를 저장하는 변수

 

pNext   : 다음 노드를 가리키는 포인터

 

pPrev    : 이전 노드를 가리키는 포인터

 

Member Values

 

 

m_pHead : 시작 노드를 가리키는 포인터

 

m_pTail : 마지막 노드를 가리키는 포인터

 

m_iCurCount : 데이터의 갯수, 노드의 갯수

 

Member Functions

 

 

push_back

 

- 새로운 데이터를 관리할 노드를 만들어준다.

 

- 이전의 노드가 없다면, Head와 Tail가 이 노드를 가리키게 해준다.

 

- 이전의 노드가 있다면 이전노드의 pNext가 새로운 노드를 가리키게 해주고 새로 생성된 노드의 pPrev가 이전노드를 가리키게 해준다. Tail은 새로운 노드를 가리킨다.

 

push_front

 

- push_back과 비슷하나 Tail대신 Head가 가리키게 된다.

 

pop_back

 

- 마지막 노드의 이전노드 pNext를 끊어주고 (NULL), 노드를 삭제해준다.

 

- Tail은 이전노드를 가리킨다.

 

pop_front

 

- 맨 앞 노드의 이후노드 pPrev를 끊어주고, 노드를 삭제해준다.

 

- Head는 이후 노드를 가리킨다.

 

reverse

 

- Head와 Tail을 바꿔준다.

 

- pPrev와 pNext를 바꿔준다.

 

clear

 

- Head부터 순회하며 모든 노드들을 삭제해준다.

 

 

empty

 

- m_iCurCount 가 0 이라면 true 아니면 false 를 리턴해준다.

 

size

 

- m_iCurCount를 리턴한다.

 

Iterator

 

Member Variable

 

 

 

m_pList : 리스트 객체를 가리키는 포이터

 

m_pNode : 현재 가리키고 있는 노드

 

Operator

 

 

 

 

Operator에 관한 설명은 생략하겠습니다.

 

코드를 보고 이해하시면 될 것 같습니다.

 

소감

 

list는 STL중 가장 구현하기 쉽습니다. STL을 구현하려고 생각하신다면 가장먼저 구현하면 좋을 것같습니다.

 

list를 구현하면 삽입삭제가 왜 빠르고 탐색이 왜 느린지 알 수 있습니다.

 

list의 다른 맴버함수들도 구현하면 좋을 것 같습니다.