링크드 리스트 : 노드로 구성된 자료구조
배열 또는 선형 리스트는
👍🏻 기본적인 자료구조 형태로 데이터를 빠른 시간 안에 조회할 수 있는 장점이 있습니다.
👎🏻 하지만, 데이터 추가/삭제 작업 후에 순서를 유지시키기 위해 데이터를 이동하는 추가적인 작업과 시간이 필요합니다.
👎🏻 또한, 크기를 변경할 수 없어 실행 속도 향상을 위해 충분히 큰 배열을 생성할 때 메모리가 낭비됩니다.
👉🏻 이러한 단점을 보완한 자료구조가 링크드 리스트 입니다.
링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있습니다.
특징
- 링크드 리스트의 원소는 원소값 필드와 다음 원소의 주소값 필드로 구성되어 있다.
- 물리적으로 데이터가 연결되어 있지 않지만, 다음 원소의 주소값을 통해 연결되어 논리적으로 연결되어 있는 구조이다.
- 리스트에서 데이터 추가 또는 삭제 시, 주소값만 수정하면 되므로, 처리속도가 빠르다. (배열 보다!)
- 이전 노드의 주소값도 함께 저장하는 더블 링크드리스트 구조도 있다.
LinkedList vs ArrayList
- 순차적으로 추가/삭제하는 경우, ArrayList가 더 빠르다.
- 중간에 데이터를 추가/삭제하는 경우, LinkedList가 더 빠르다.
👉🏻 데이터의 개수가 고정이면, ArrayList가 최상의 선택이 될 수 있지만,
데이터의 개수가 변동이 자주 있다면, LinkedList를 사용하는 것이 더 나은 선택이 될 것이다.
'자료구조' 카테고리의 다른 글
| Array vs Arraylist (0) | 2023.01.10 |
|---|