Array와 Linked List

Array

• 선형 자료구조의 하나로 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 구조이다.
• 논리적 저장 순서와 물리적 저장 순서가 일치하다는 특징이 있다.
  
• 인덱스를 알고 있다면 접근(search)의 시간 복잡도는 O(1) 이다.
• 삽입(insert)과 삭제(delete)의 시간 복잡도는 각 작업을 하고 난 뒤, 나머지 요소들을 shift해줘야 하기 때문에 O(n) 이다.
• Stack 영역에 할당된다.

Linked List

• 선형 자료구조의 하나로 Array 자료구조에서 삽입과 삭제에 O(n)의 시간이 걸리는 것을 보완하기 위해 나왔다.
• 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는다.
  
• 접근(search)의 시간 복잡도는 O(n) 이다.
• 삽입(insert)과 삭제(delete)의 작업 자체의 시간 복잡도는 O(1)이지만, 해당 요소를 찾기 위해 O(n)이 요소되므로 결국 O(n) 이다.
• Heap 영역에 할당된다.

시간 복잡도에 대해서...

위에서 Array와 Linked List의 접근, 삽입, 삭제에 걸리는 시간 복잡도를 알아봤는데 이는 사실 어느 상황이냐에 따라 조금씩 다르다. 다음 표를 첨부할테니 살펴보고 왜 그런지에 대해서도 한 번 생각해보면 좋을 것 같다.

	Array List	Linked List
접근	⍬(1)	⍬(n)
맨 앞에서의 삽입/삭제	⍬(n)	⍬(1)
맨 뒤에서의 삽입/삭제	⍬(1)	마지막 요소를 알고 있을 때 ⍬(1) 마지막 요소를 모르고 있을 때 ⍬(n)
임의의 위치에서 삭입/삭제	⍬(n)	탐색시간 + ⍬(1)
최악의 경우	⍬(n)	⍬(n)

(출처: https://sdesigner.tistory.com/73)

Stack과 Queue

Stack

• 선형 자료구조의 일종으로 Last In First Out(LIFO), First In Last Out(FILO)이다.
  

Queue

• 선형 자료구조의 일종으로 First In First Out(FIFO)이다.