틈새 면접 질문:
배열과 연결리스트는 선형 자료구조이다. 이 둘의 차이를 설명하라.
오늘은 연결 리스트에 대해 알아보겠다. 알고리즘 공부는 바킹독의 유튜브로 진행하고 있으며 그중 4강 연결 리스트와 백준 문제를 가지고 공부할 것이다.
https://www.youtube.com/watch?v=C6MX5u7r72E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=5
바킹독 - 00x4 연결리스트
(선형 자료구조)
연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조입니다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음 노드와의 연결을 담당합니다.
배열에 비해서 데이터의 추가/삭제가 용이하나, 인덱스가 없는 리스트의 특징으로 인하여 특정 요소에 접근하기 위해서는 순차 탐색을 필요로 하므로 일반적으로 탐색 속도가 떨어집니다. 즉, 탐색 또는 정렬을 자주하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것을 권장합니다. (자바 LinkedList의 경우 인덱스를 사용하여 연산을 수행할 수 있도록 get(index) 형태의 메서드를 제공하지만, 메서드 내부의 동작은 순차 탐색으로 이루어져 있습니다)
다음은 연결 리스트의 종류입니다.
- 단일 연결 리스트(Singly Linked List)
각 노드가 다음 노드에 대해서만 참조하는 가장 단순한 형태의 연결 리스트입니다.
일반적으로 큐를 구현할 때 사용됩니다.
Head 노드를 잃어버려 참조하지 못하는 경우 데이터 전체를 사용 못하게 되는 단점이 있습니다.
FAT 파일 시스템이 단일 연결 리스트로 파일 청크(동적 메모리로 할당되는 영역)를 연결합니다. - 이중 연결 리스트(Doubly Linked List)
각 노드가 이전 노드, 다음 노드에 대해서 참조하는 형태의 연결 리스트입니다.
삭제가 간편하며 단일 연결 리스트에 비해 데이터 손상에 강하지만, 관리할 참조가 2개이기 때문에 삽입이나 정렬의 경우 작업량이 더 많아집니다.
- 원형 연결 리스트(Circular Linked List)
연결 리스트에서 마지막 요소가 첫번째 요소를 참조합니다.
스트림 버퍼의 구현에 많이 사용됩니다.
참고 자료, 블로그: https://freestrokes.tistory.com/84
Java로 연결 리스트(Linked List) 구현하기
Java로 연결 리스트(Linked List) 구현하기 Java로 연결 리스트(Linked List)를 구현하는 방법에 대해 알아보겠습니다. 1. 연결 리스트(Linked List) 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄
freestrokes.tistory.com
'개발일지 > 알고리즘' 카테고리의 다른 글
| [그리디 알고리즘] (0) | 2024.05.12 |
|---|---|
| [Algorism 알고리즘] Stack 스택 (수정중) (0) | 2024.03.06 |
| 내가 보려고 만든 알고리즘 공부를 위한 북마크💾 (1) | 2024.02.24 |
| [Algorism 알고리즘] 배열 (0) | 2023.03.16 |
