자료구조, 리스트에 관해서

Question

윤성우의 자료구조라는 책의 리스트 부분을 공부하고 있습니다.책에서 c언어로 리스트와 리스트 관련 연산함수들을 직접 구현하고 있는데 여기에 LFirst와 LNext라는 함수가 있습니다.LFirst는 리스트의 첫번째 데이터를 참조하는 것이고, LNext는 이전에 참조한 것 다음 데이터를 참조하는 함수입니다. 배열처럼 인덱스로 참조하지 않고 이렇게 하는 이유가 무엇인지 궁금합니다. 리스트는 배열과 달리 중간에 값이 하나 삭제되면 뒤에있는 값들을 앞으로 하나씩 가져와야 되서 그런건가요?

Giolitti · Accepted Answer

유연하게 자료를 생성, 삭제, 추가 하려면 사이즈가 정적으로 정해지는 배열은 어렵습니다.동적으로 배열을 생성한다고 해도 결국 만들어진 사이즈를 초과하면 다시 더 큰사이즈의 배열을 만들어 그전 배열에서 전부를 복사해야하죠. 더큰사이즈의 배열에 복사하고 나면 배열의 남은 부분은.. 낭비가 되죠. 결국 메모리 많이 먹습니다. 이게 무조건 문제라는게 아니라 데이터의 수가 정확하지 않다고 하면 이렇게 구현하는건 잘못된 방향이라는거죠.리스트는 최소 사이즈의 배열을 동적으로 계속해서 만들어서 배열이 생성되면 이전 배열과 신규 배열을 연결시켜 주는거라고 보시면 됩니다. 삭제도 그렇고요.list, map, sete등 다양한 자료구조는 언어 특성에 따라 다르겠지만 라이브러리로 전부 제공하고 있습니다. 하지만 자료구조를 직접 구현해보면서 자료구조의 특성을 알면 올바른 자료구조를 사용하거나 다른분이 구현한 코드를 분석할 때 도움이 됩니다.LFirsts 가 존재하는 이유는 리스트의 head가 무조건 저장되어 있어야 합니다. 손실되면 리스트 찾을 수 없기 때문에 해당 리스트의 모든 메모리 영역은 메모리릭이 발생됩니다. LNext는 연결된 모든 리스트를 검색하기 위해 필요합니다.그리고 삭제된 리스트를 제거하고 남은 리스트를 연결하기 위해 필요합니다.// Pseudo Code로 짜보면 대략 다음과 같습니다.previoisNode; // 삭제할 노드의 앞 노드deleteNode; // 삭제될 노드previousNode->LNext &#61; deleteNode->LNext; // 삭제될 노드의 앞노드와 뒷노드를 연결함.delete(deleteNode); // 삭제될 노드를 메모리에서 삭제함

Clickin · Answer

Linked List라는 개념을 공부해보시면 됩니다.

자료구조, 리스트에 관해서

2개의 답변

기타 목록