앞 장에서 기본적인 자료구조(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장 : 스택과 큐
피드 구독하기:
댓글 (Atom)
인기글
-
언젠가부터 내 스마트폰에서 용량이 부족 하다면서 계속 알림이 떴다. 저가폰이라 내부저장소가 16GB 밖에 되지 않았지만, 추가로 마이크로SD 카드 16GB를 달았는데도 그렇다. 안드로이드가 앱을 설치하고 필요한 데이터를 저장하는 곳은 특별히 지정하...
-
나는 무려 10년이 된 Java 프로젝트를 여러개 관리하고 있는데, Netbeans와 Ant 기반의 개발/빌드 환경을 사용한다. Netbeans는 Sun이 Oracle로 넘어간 뒤에 Apache 재단으로 넘어가면서 개발 동력이 많이 떨어져 있다...
-
알톤 니모 전기자전거를 구입한지 2주일째다. 지금까지 출퇴근 용으로 잘 쓰고 있다. 굉장히 만족하고 있다. 주행기에 대해서는 한달 정도 탄 후에 올려볼까 한다. 전기자전거를 알아볼때 느낀건데, 매뉴얼이 공개되어 있지 않아 자세한 정보를 얻기 어려...
댓글 없음:
댓글 쓰기