배열과 연결리스트

배열(Array)

배열은 가장 기본적인 자료구조로, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소에 접근할 수 있고, O(1)의 시간만에 해당 원소에 접근할 수 있다.

하지만 원소를 삽입, 삭제하는 경우에는 뒤의 원소들을 한칸씩 shift 해줘야하기 때문에 O(n)의 시간이 걸린다.

 

연결리스트(Linked List)

연결리스트는 원소 각각이 자기 자신 다음 순서가 어떤 원소인지만 기억한다.

그래서 어떤 특정 인덱스의 원소에 접근하기 위해서는 첫번째 원소부터 순차적으로 검색해야 하므로 O(n)의 시간이 걸린다.

어떤 특정 원소의 주소를 알고 있을 때 그 원소를 삭제하던가 삽입하는 시간은 O(1)의 시간이 걸리지만, 주소를 모르고 몇번째 원소인지(인덱스)만 알고 있다면 마찬가지로 삽입, 삭제에 O(n)의 시간이 걸린다. 

 

연결리스트는 단순하게 썼을 때는 시간효율성이 나쁜 것처럼 보이지만, Tree구조의 근간이 되는 자료구조이다.

 

참고

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linked-list