[자료구조] 배열(Array) vs 연결 리스트(LinkedList) 핵심 비교

배열 (Array)

• 연속 공간에 값이 채워져 있는 형태의 자료구조입니다. 
• 인덱스를 통해 참조할 수 있으며, 선언한 자료 값만 저장 가능합니다.
• 배열 선언 시 크기를 지정하고 이후 크기를 조정할 수 없습니다. 
• 조회 및 수정에는 O(1), 삽입 및 삭제에는 O(n)으 복잡도를 가집니다.

인덱스를 통한 접근

 

삽입 및 삭제

 

리스트 (Lincked List)

• 값과 포인터들을 묶은 노드라는 것을 포인터로 연결한 구조입니다. 
• 선언 시 크기를 별도로 지정하지 않아도 됩니다. (가변적)
• 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡합니다. 
• 값의 접근을 위해서는 Head(처음)부터 순서대로 접근해야 하므로 O(n) 복잡도가 걸립니다.
• 포인터로 연결이 되어 있어 데이터를 삽입하거나 삭제하는 데에는 O(1) 복잡도가 걸립니다. 

데이터 접근

 

데이터 삭제

 

 

배열과 리스트를 다시 정리해 보니, 앞으로는 코드를 작성하기 전에 '이 데이터는 어떻게 사용될까?'라는 질문을 먼저 던져야겠다는 생각이 들었습니다. 결국 좋은 성능을 내는 코드란 데이터의 특성에 맞는 자료구조를 선택하는 작은 디테일에서부터 시작된다는 것을 느꼈습니다.