Array(배열), Linked List(리스트), 둘의 차이점

자료구조와 알고리즘은 왜 배워야 하는 것일까?
: 특정 자료구조는 삽입/삭제가 빠르고, 특정 자료구조는 조회가 빠릅니다.

 

이처럼 어떤 경우에는 이 자료구조가 좋고, 어떤 경우에는 저 자료구조가 좋은 것 처럼

경우에 따라 다양한 자료구조와 알고리즘을 사용 해야 합니다.

 

비유를 하자면

못을 박을 때 망치가 필요하고, 나사를 뺄 때는 뺀치가 필요한 것처럼 다양한 공구들을 하나하나 배워 나가는 것이라고 생각하면 됩니다.

---

1. 어레이(Array), 배열

상황으로 어레이를 설명 해보자면!

상황에서 언급된 "캡슐 호텔'이란 바로 Array, 배열을 의미합니다.

 

👀 여러분이 캡슐 호텔을 만들었습니다! 총 8명이 잘 수 있는 호텔입니다. 와 그런데 이게 무슨일일까요?

오늘 밤에 소녀시대 8명 전원이 와서 숙박할 계획이라고 합니다.

👉 베열은 크기가 정해진 데이터의 공간이고, 한번 정해지면 바꿀 수 없다.

 

rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "서현"]

 

👀 떨리는 마음으로 체크인을 받고, 각 호수에 있는 멤버들의 방에 방문해 웰컴 드링크를 전달했습니다.

👉 배열은 각 호텔방(원소)에 즉시 접근 할 수 있습니다. -> rooms[0]처럼!

여기서, 원소의 순서는 0부터 시작하고 이를 "인덱스"라고 부릅니다.

 

이때, 즉시 접근 가능하다는 말은 상수 시간 내에 접근 할 수 있음을 의미하기 때문에

즉, O(1) 내에 접근 가능하다고 말하곤 합니다.

 

👀 앗 그런데, 제일 끝방에 있는 서현이 수영과 티파니 사이의 방에서 자고 싶다고 합니다. 다른 멤버들의 순서는 유지한채요! 그래서 다음과 같이 이동해야 했습니다. 너무 힘들게 방을 옮겨서 피곤해진 서현이는 바로 곯아떨어졌다고 합니다. * 참고로 코딩에서 변수를 옮길 때 한번에 하나씩 옮길 수 있어서 두명씩 방을 옮기게 됩니다

👉 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 합니다.

최악의 경우 배열의 길이 N만큼을 옮겨야 하므로 O(N) 만큼의 시간 복잡도를 가지게 됩니다.

# 처음 상태
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "서현"]

# 1번 이동 -> 써니와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "서현", "써니" ]

# 2번 이동 -> 태연과 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "서현", "태연", "써니" ]

# 3번 이동 -> 유리와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "서현", "유리", "태연", "써니" ]

# 4번 이동 -> 효연과 서현 변경
rooms = ["윤아", "수영", "티파니", "서현", "효연", "유리", "태연", "써니" ]

# 5번 이동 -> 티파니와 서현 변경! 후! 드디어 도착!
rooms = ["윤아", "수영", "서현", "티파니", "효연", "유리", "태연", "써니" ]

 

👀 갑자기 호텔 프론트에 전화가 왔습니다. 매니저가 곧 도착할 예정이니, 방 하나를 더 준비해달라고 연락이 왔습니다! 이런, 어떡하죠? 그래서 옆 공터에 방이 9개인 호텔을 지었습니다. 물론 새로운 호텔을 짓느라 돈과 시간을 다 써 사업이 망해버리고 말았습니다 ㅠㅠ

👉 배열에서 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조임을 알 수 있다.

---

2. 링크드 리스트(Linked List), 리스트

상황으로 링크드 리스트를 설명 해보자면!

상황에서 언급된 "화물 열차'란 바로 Linked List, 리스트를 의미 합니다.

 

👀 여러분이 이번엔 화물 열차를 만들었습니다. 총 5칸을 실은 화물 열차입니다.

각 화물칸은 다음 칸을 연결짓는 연결고리로 이어져 있습니다!

👉 리스트는 크기가 정해지지 않은 데이터의 공간입니다.

연결고리로 이어주기만 하면, 자유자재로 늘어날 수 있습니다.

train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

 

👀 우편 칸에 잠시 일이 생겼습니다! 시멘트 칸을 지나, 자갈칸을 지나, 밀가루 칸을 지나 겨우 우편칸에 도착했습니다.

👉 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색 해야 합니다.

최악의 경우에는 모든 화물 칸을 탐색해야 하므로 O(N)의 시간 복잡도를 가집니다.

여기서, 앞으로 연결 고리를 포인터라 부르고, 각 화물 칸을 노드라고 부르겠습니다.

# 처음 상태              내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

# 1번 이동                           내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

# 2번 이동                                      내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

# 3번 이동                                                 내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

# 4번 이동                                                             내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

 

👀 앗 그런데, 시멘트 칸과 자갈 칸 사이에 흑연이라는 칸을 넣기로 했습니다. 그래서, 화물칸의 연결고리를 이어 붙였습니다. 시멘트 칸의 연결고리를 흑연 칸에 연결하고, 흑연 칸의 연결고리를 자갈 칸으로 연결했습니다.

👉 리스트는 원소를 중간에 삽입/삭제하기 위해서는 앞,뒤의 포인터만 변경하면 됩니다.

따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있습니다.

# 처음 상태
["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
                              ["흑연"] 을 중간에 넣어야 합니다

# 1. 자갈 칸의 연결고리를 흑연 칸으로 연결하고,
["자갈"] -> ["흑연"]   ["밀가루"] -> ["우편"]

# 2. 흑연 칸으로 연결고리를 밀가루 칸으로 연결합니다. 
["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]

 

👀 가던 도중 밀가루가 상해서 밀가루 칸을 버리기로 했습니다. 그래서 흑연 칸의 연결고리를 떼서 우편 칸으로 연결하기로 했습니다! 밀가루 칸을 버려버렸습니다.

👉 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞, 뒤의 포인터만 변경하면 된다.

따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있습니다.

# 현재 상태
["기관실"] -> ["시멘트"] -> ["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]
                                              ["밀가루"] 칸을 버려야 합니다

# 흑연 칸의 연결고리를 떼서, 우편 칸으로 연결하면 됩니다!
["흑연"]     ->      ["우편"]  
        ["밀가루"]

---

3. 어레이와 링크드 리스트의 차이점

---

4. 한발자국 더!

이 설명을 보면 자바스크립트의 배열도 pop, push 등등을 사용해서 원소(요소)를 삽입하고 삭제 할 수 있기 때문에

내부적으로 동적 배열이라는 걸 사용해서 배열의 길이가 늘어나도 O(1)의 시간 복잡도가 걸리도록 설계 된 것 같다!

 

그렇기 때문에 자바스크립트의 배열도 링크드 리스트로 쓸 수 있고, 배열로도 쓸 수 있게 만들어진 효율적인 자료구조다