배열 VS 연결리스트
[2023.05.26 ~ 2023.06.01] 동안 공부한 배열과 연결리스트이다.
해당 포스트는 누구나 자료구조와 알고리즘 개정 2판을 참고하여 작성되었다.
📌 배열 VS 연결리스트
연결리스트(LinkedList)
✔ 연결리스트는 가장 간단한 노드 기반 자료 구조이다.
노드란 컴퓨터 메모리에 여기저기 위치해있는 데이터 조각이다.
- 노드기반 자료는 데이터를 조작하는 데 성능상 큰 이점이 많다.
연결리스트란
연결리스트는 배열처럼 여러가지 값을 담고있는 자료구조이다.
컴퓨터안의 메모리는 데이터조각(노드)를 저장하는 셀들의 모음이다. 코드에서 배열을 만들면 메모리 안에서 이어진 빈 셀 그룹을 찾아 데이터를 할당한다.
연결리스트는 배열과 다르게 연속된 노드 조각 모음이 아니라 여기저기 펼쳐져 있을 수 있다.
메모리 안에서 인접해있지 않은데 어떻게 같은 리스트에 속해있다고 알 수 있을까?
바로 연결리스트의 핵심, 링크이다. 연결리스트는 링크를 통해 서로 연결연결되어있다. 연결리스트의 노드는 메모리 셀 2개를 가지고 있다.
- 실제 데이터
- 연결된 다음 노드의 메모리 주소 값
- 연결리스트의 첫번째 노드를 헤드(head), 마지막 노드를 테일(tail)이라고 부른다.
- 컴퓨터 메모리안에 데이터가 꼭 연속되지 않아도 된다는 점에서 연결리스트가 배열보다 유리할 수 있다.
읽기
읽기는 특정 인덱스의 값을 읽는다.
배열의 읽기에서는 어떤 원소든 O(1) 이지만 연결리스트에서는 첫번째 노드는 O(1), 최악의 경우에는 O(N)이 될 수 있다..
| case | 배열 | 연결리스트 |
|---|---|---|
| 읽기 | O(1) | O(N) |
검색
검색은 값을 찾아 값의 인덱스를 반환한다.
연결리스트의 검색도 마찬가지이다. 어떠한 값을 찾을때, 첫번째 인덱스부터 값을 비교하여 링크를 타고 계속 검색을 이어간다. 최선의 경우 O(1)이고, 최악의 경우 O(N)이다.
| case | 배열 | 연결리스트 |
|---|---|---|
| 검색 | O(N) | O(N) |
연결리스트 왜 써?!?
검색과 읽기에서 본다면 연결리스트 보다 배열을 쓰는 것이 훨씬 성능 상 이점이 크다. 그럼에도 불구하고 배열보다 연결리스트가 유용한 순간이 존재한다 ‼
삽입에서 연결리스트가 배열보다 성능상 이점이 크다. 🙆♀️
삽입
배열 삽입에서는 마지막 인덱스의 값을 삽입하지 않는 이상, 값이 없는 빈 공간을 채우기위해 값을 꼭 오른쪽으로 시프트해야하므로 O(N)이 소요된다.
반면 연결리스트는 맨 앞에 삽입하는 경우, 딱 O(1) 이 소요된다 ✨
하지만 리스트 끝에 첫번째 노드를 통해 접근해야하므로 삽입하는 경우 검색 O(N), 삽입 O(1) 총 O(N)의 시간이 걸린다.
배열과 달리 연결리스트는 하나도 시프트하지 않고 리스트 바로 앞에 데이터를 삽입할 수 있다.
| case | 배열 | 연결리스트 |
|---|---|---|
| 앞에서 삽입 | 최악💩 | 최선 |
| 중간에서 삽입 | 평균 | 평균 |
| 끝에서 삽입 | 최선 | 최악 💩 |
삭제
예를 들어 배열 삭제에서는 첫번째 인덱스를 삭제할때, 첫번째 인덱스가 공백이 되므로 나머지 배열의 값들을 왼쪽으로 시프트해야하므로 O(N) 단계가 걸린다. 연결리스트에서는 첫번째 노드를 삭제할때, 원래 첫번째 노드와의 연결을 끊고 두번째 노드를 첫번째 노드(Head)로 만들면 되므로 O(1) 단계가 걸린다.
하지만 연결리스트의 마지막 노드를 삭제하려고 한다면, 첫번째 노드부터 접근이 가능하므로 타고 들어가서 마지막 노드를 찾은 후 삭제해야하므로 O(N) 단계가 걸린다.
연결리스트에서 노드를 삭제한다는 것은 현재 리스트와의 연결고리를 끊는다는 것이다. 메모리에서 제거한다는 의미는 아니다.. ‼
| case | 배열 | 연결리스트 |
|---|---|---|
| 앞에서 삭제 | 최악 💩 | 최선 |
| 중간에서 삭제 | 평균 | 평균 |
| 끝에서 삭제 | 최선 | 최악 💩 |
연결리스트를 어떠한 상황에서 쓸까
배열을 사용했을 때 최악 시간복잡도가 나오는 경우, 연결리스트를 쓰는 게 나을 수 있다. ✨
예를 들면 리스트를 검사해서 많은 값을 삭제할 때이다.
리스트의 길이가 길수록 배열은 값을 삭제하면서 매번 긴 시프트의 과정을 거쳐야하지만 연결리스트는 검색해서 연결만 끊어주면 되므로 배열보다 시간 복잡도가 훨씬 줄어든다.
리스트의 길이가 1,0000 개라 했을 때 배열은 매번 값을 검사하고, 삭제하면서 매번 1,0000 개 이하의 값을 시프트 해야할지 모른다… 최악의 경우 1,0000 * 1,0000 일 수 있다.. 하지만 연결리스트는 1,0000번의 검사 후 개수만큼의 삭제를 하면 되므로 시간 복잡도가 훨씬 줄 수 있다. 🙆♀️
