알고리즘 단련장/자료구조와 알고리즘 강의
연결리스트(Linked Lists)
dcho
2022. 9. 2. 17:14
SMALL
연결리스트(Linked Lists)
선형 배열과는 다르다. 선형 배열은 "번호가 붙여진 칸에 원소들을 채워 넣는" 방식이라면 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식이다.
장점으로는 삭제하거나 삽입하는것이 선형 배열의 경우보다 쉽다. (빠른 시간 내에 처리할 수 있다는 뜻)
이러한 이점 때문에, 원소의 삽입/삭제가 빈번히 일어나는 경우에는 연결 리스트가 많이 이용됩니다. 컴퓨터 시스템을 구성하는 중요한 요소인 운영체제(Operation System)의 내부에서도 이러한 연결 리스트가 여러 곳에서 이용되고 있습니다.
단점으로는 선형 배열에 비해 데이터 구조 표현에 소요되는 저장 공간(메모리) 소요가 크다. 또 "i번째의 원소"를 찾아가는 데에 시간이 더 걸린다.(앞에서부터 하나씩 링크를 따라가면서 찾아가야 하기 때문)
연결 리스트의 핵심 연산으로써 아래와 같은 것들이 등장
- 원소의 삽입(insertion)
- 원소의 삭제(deletion)
- 두 리스트 합치기(Concatenation)
이러한 연산이 쉽게(빠르게) 이루어질 수 있다는 점이 연결 리스트가 선형 배열에 비하여 가지는 특장점이다. 조금 다르게 표현하면, 이런 연산들이 빨라야 하는 응용처에 적용하기 위함이 연결 리스트의 존재 이유이다.
본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.