들어가며

이번에는 연결 리스트에 대해 정리해 보려고 합니다.

---

리스트

리스트(List)란?

리스트는 순서를 가진 데이터의 모음을 말합니다.

리스트 주요 연산

리스트의 주요 연산으로는 원소의 삽입, 삭제, 검색, 참조가 있습니다.

리스트 구현 방법

리스트를 구현하는 방법으로는 배열 또는 연결 리스트를 사용하는 방법이 있습니다.

• 배열은 연속된 메모리 공간을 사용하기 때문에 원소의 삽입, 삭제가 비효율적입니다.
• 연결 리스트는 임의의 메모리 공간을 사용하기 때문에 원소의 삽입, 삭제가 배열에 비해 효율적입니다.

연결 리스트

연결 리스트(Linked list)란?

연결 리스트는 데이터와 포인터로 구성된 노드가 연결되어 있는 방식으로 데이터를 저장하는 자료 구조를 말합니다.

연결 리스트 장단점

• 장점 : 리스트에 원소의 삽입, 삭제가 효율적으로 일어나며, 크기 제한이 없습니다.
• 단점 : 리스트의 원소에 접근이 비효율적으로 일어나며, 데이터를 저장할 때 포인터를 위한 여분의 공간이 필요합니다.

연결 리스트 구현

구조체와 클래스를 이용해 원소의 삽입, 삭제가 가능한 간단한 단방향 연결 리스트를 구현해 보았습니다. Github에서 코드 보기.

---

포스팅을 마치며

잘 하려다보니 점점 포스팅이 느려지네요.

Reference

황선규. C++ 어서와! 자료 구조와 알고리즘은 처음이지?. Programmers.