연결리스트 구현에 관한 질문입니다.
글쓴이: exsider / 작성시간: 월, 2003/11/03 - 10:16오후
제가 하는 과제에 연결리스트를 구현하는게 있는데요,
class ListNode
{
..... // 연결리스트의 노드를 나타냄
};
class List
{
private:
static ListNode * ptr; // 안쓰는 노드를 연결해 두었다가
// 나중에 필요할 때 꺼내 씀
...
};
대충 구조가 이런데요, ptr 에는 List 에서 삭제한 노드를 따로 연결해 두었다가
자료를 넣을 때 여분의 노드가 있을 경우 새로 할당하지 않고 여기서 가져다
씁니다.
제가 궁금한 건 ptr 에 연결되어 있는 노드들도 프로그램이 종료할 때는 삭제
해야 할텐데 이걸 어떻게 할 것인가 입니다. 따로 안해도 운영체제에서 알아서
해줄 것이란 생각이 들기는 하는데 아무래도 직접처리하는 것이 더 낫지 않을까 하는 생각이 듭니다.
제가 생각하기에는 ListNode * 대신에 별도의 컨테이너 클래스를 사용하고
레퍼런스 카운트 같은 걸 사용해서 List 객체가 하나도 없을 때 자동 소멸되게 하는방법이 괜찮은 것 같은데요, 혹시 더 나은 방법이 있을 까요???
Forums:
~List() 에서 지워주시면 되겠지요.
~List() 에서 지워주시면 되겠지요.
소멸자에서 실행하면 됩니다.
C++에서는 소멸자라고 하지여? C++에서는 프로그램이 종료될때 자동으로 메모리를 해제 시켜주지 않습니다. 소멸자를 사용자가 구현해 주어야 합니다.
~List()에서 삭제 하면 됩니다. 프로그램이 종료될때 실행되니까여.
List()에서 삭제된 노드를 연결시킬 메모리를 할당하면 되겠지여. :D
good job
제가 설명을 제대로 못했나 보네요. ptr 은 여분의 노드를 가지
제가 설명을 제대로 못했나 보네요.
ptr 은 여분의 노드를 가지고 있다가 새로 노드가 필요할 때 가져다 쓰는 것입니다.
이런식으로 하면 불필요한 메모리 할당을 막을 수 있죠.
List 클래스의 소멸자에서는 자신이 가지고 있던 노드를 ptr 에 넘깁니다.
(삭제되는 노드는 모두 ptr 에 물려 두지요.)
List::~List() { 현재 객체가 가진 마지막 노드의 next 를 ptr 의 next 로 세팅한다. ptr 이 현재 객체가 가진 처음 노드를 가리키게 한다. }소멸자는 대략 이런식입니다.
따라서 소멸자에서는 ptr 에 연결되어 있는 노드를 삭제할 수 없습니다.
글쎄요. 적어주신 내용만으로 보기에는 어떤 식으로 구현을 하셨는지 잘 모
글쎄요. 적어주신 내용만으로 보기에는 어떤 식으로 구현을 하셨는지 잘 모르겠네요. 리스트가 단순한 대학교2학년 숙제라고 생각하는 분들을 꽤 많이 보았는데, 실제로 리스트를 제대로 모델링하려면 고려해야 할 것이 꽤 많습니다.
일단 그냥 적어주신 내용으로만 본다면 Container와 Iterator가 확실히 구분될 필요가 있다는 느낌이 드는군요. 분명히 올려주신 간단한 코드+ ~List()의 설명대로라면 exsider님께서 생각하는 리스트의 구조는 잘못된 것입니다. 왜 그런지는 잘 생각해보셨으면 합니다.
List의 인터페이스는 쉬운것 같으면서도 알고보면 참 복잡하지요. 예를 들면 ListNode가 정말 필요한가 필요하지 않은가부터, List 자체가 ListNode에서 사용하는 메모리를 관리해줄것인가 그렇지 않을것인가, 만일 ListNode의 메모리구조가 다른 구조를 다시 사용한다면 이녀석들을 deep하게 또는 shallow 하게 처리할 것인가.. (이런 문제는 delete, copy등에 동일하게 적용됩니다) 등등...
GoF의 list 패턴부터, g_list, QList 등에서 사용한 구현 방식, 오픈 소스로 돌아다니는 셀수없이 많은 자료구조 라이브러리들(C, C++, java)을 이것저것 검토해보신다면 제가 적어놓은 내용에 공감하실 것 같습니다.
댓글 달기