앞 장에서 기본적인 자료구조(Data Structure)로서 랜덤억세스에 강점이 있는 배열에 대해 살펴 보았습니다. 이번 장에서는 순차적 접근을 염두에 두고 고안된 연결리스트(Linked List)에 대해서 살펴 봅니다.연결리스트는 정보를 저장하는 노드와 노드간의 연결을 저장하는 링크로 구성됩니다. 노드 하나에 다음 노드로의 링크 하나가 있는 걸 단순 연결리스트라 하고, 노드 하나에 앞 뒤의 연결을 나타내는 두개의 링크가 있으면 이중 연결리스트라고 합니다.
이렇게 연결 리스트는 노드의 연결 상태를 바로 앞뒤의 링크로 저장하기 때문에 순차적인 접근만이 가능합니다. 이런 단점에도 불구하고 연결리스트의 중간에 노드를 추가하거나 노드를 삭제할 때는 매우 좋은 성능을 보여줍니다. 그리고 데이터 집합 갯수가 유동적일 때 최대치를 미리 잡아놓지 않아도 필요한 만큼만 메모리를 할당하여 사용할 수 있는 장점도 있습니다.
연결리스트의 구현을 통해 C++의 포인터(Pointer)에 대해서도 연습을 할 수 있습니다. 아마도 C++을 배울 때 가장 어려운 난관 중의 하나가 포인터일 겁니다. 그런 의미에서 이번 장은 매우 중요합니다.
강의 파일
동영상 파일
5.0 연결리스트 - 시작 : 자료구조를 배우는데 첫번째 난관이 될 연결리스트(Linked List)입니다. 연결리스트에 대해 배울 내용들을 살펴봅니다.
5.1 연결리스트의 개념 : 연결리스트의 기본적인 개념과 구현을 위해 필요한 템플릿과 예외처리에 대한 내용을 배워 봅니다.
5.2 단순 연결리스트 : 하나의 링크만 가지는 단순 연결리스트의 개념을 살펴보고 구현해 봅니다.
5.3 단순 연결리스트의 사용법 : 단순 연결리스트를 실제로 사용하는 법에 대해 비쥬얼 C++을 이용하여 시연합니다.
5.4 이중 연결리스트 : 링크가 두개인 이중 연결리스트의 개념과 기본 구현에 대해 알아 봅니다.
5.5 이중 연결리스트의 사용법 : 앞에서 구현한 이중 연결리스트를 실제로 사용하는 법과 동작하는 원리를 디버거를 통해 알아 봅니다.
5.9 연결리스트 - 결론 : 이번 장에서 배운 연결리스트를 정리해 봅니다.
관련글 |
- C++로 배우는 알고리즘
- 4장 : 배열과 미로 탐색
- 6장 : 스택과 큐
댓글 없음:
댓글 쓰기