연결 리스트(Linked List) 용도/사용빈도
1. 배열의 한계를 극복하기 위해
배열(or 배열 기반 리스트)의 한계
- 배열은 정형화돼서 색인으로 접근해야 합니다.
- 초기에 메모리 공간을 잡아두고, 변경이 불가능합니다.
- 삭제 시 데이터의 이동(복사)가 빈번히 발생합니다.
하지만 연결리스트는 메모리 크기가 얼마인지 중요하지 않습니다. 노드 하나 만들어 놓고 필요할 때마다 만들어 연결하기 때문에 길이가 자유롭습니다. 데이터를 삽입/삭제할 때도 위치만 안다면 삭제하고 복사할 필요없이 진행할 수 있습니다.
이런 개념은 연결 리스트는 배열보다 메모리를 좀 더 자유롭게 사용하면서 다음 것(데이터)를 가리킬 수 있는 방식으로 볼 수 있습니다.
2. 삽입, 삭제가 빈번한 경우에 사용
연결 리스트에서는 삽입, 삭제를 위해 복사하고 당기는 경우가 없습니다.
왜 그런지 좀 더 이해하고 싶다면 아래 글을 참고해주세요.
연결리스트(Linked List) 삽입/조회(그림으로 이해하기)
연결리스트(Linked List) 삭제 (그림으로 이해하기)
3. 커널 모드 프로그래밍에서 사용
커널 모드 성능상 데이터를 굉장히 빠르게 처리해야하기 때문에 삽입/삭제가 자유로운 연결 리스트를 사용합니다.
과거에 사용돼었던 것이 지금까지 유지되는 경우도 있습니다.
※ 사실 오늘날 어플리케이션 프로그램에서 연결 리스트의 사용 빈도는 많이 줄었습니다.
그 이유는 하드웨어 발전이랑 관련이 있습니다. CPU에 들어가는 캐시 메모리는 연속된 메모리에 접근할 때 굉장히 빠른 속도를 보장합니다. 따라서 이 부분에 있어서 연결 리스트보다는 배열이 더 유리합니다. 그래서 연결 리스트보다는 다른 언어의 다른 자료구조가 더 활용되고 있는데 그 중 하나가 C#언어의 리스트입니다. 다른 말로 동적 배열입니다. 배열로 잡아두고 배열 크기가 커지면 크기만 바뀌는 개념입니다.
------------------------------
------------------------------
'컴퓨터 공학 > Algorithm' 카테고리의 다른 글
| [알고리즘] 스택(Stack)의 삽입/제거/검색(C언어) (405) | 2020.07.10 |
|---|---|
| [ 알고리즘 ] 스택(Stack)의 개념과 용도 (400) | 2020.07.10 |
| [ 알고리즘 ] 추상 자료형(ADT) 란? (406) | 2020.07.09 |
| [ 알고리즘 ] 연결리스트(Linked List) 삽입/조회(그림으로 이해하기) (402) | 2020.07.09 |
| [ 알고리즘 ] 하노이 타워(The Tower of Hanoi) 재귀 함수로 구현하기 (C언어) (405) | 2020.07.09 |
댓글