[백엔드] 기술 면접 Top30 - #28 Array, LinkedList

Array, LinkedList

 

 

Array ( 배열 )

• 연속적인 메모리 공간에 동일한 데이터 형식의 요소들을 저장하는 선형 데이터 구조이다. 
• 인덱스를 사용하여 요소에 접근할 수 있으므로 빠른 읽기와 쓰기 연산이 가능하다. 
• 요소의 크기가 고정되어 있으며, 크기를 동적으로 변경하기 어려우므로 배열을 생성할 때 크기를 결정해야 한다. 
• 요소를 추가하거나 삭제할 때 다른 요소들을 밀거나 당겨야 할 수 있어 삽입과 삭제 연산이 비효율적일 수 있다. 
• 배열은 메모리에 연속적으로 저장되므로 캐시 효율성이 좋아 빠른 접근이 가능하다.
  
  

LinkedList ( 연결 리스트 )

• 각 요소가 자신의 데이터와 다음 요소를 가리키는 링크(포인터)를 포함하는 데이터 구조이다. 
• 동적으로 크기를 조절할 수 있으므로 삽입과 삭제 연산이 배열에 비해 효율적이다. 
• 요소에 접근할 때는 처음부터 시작하여 순차적으로 접근해야 하므로 읽기 연산은 배열에 비해 느릴 수 있다. 
• 더블 링크드 리스트와 같이 이전 요소를 가리키는 링크를 추가하면 역방향으로도 순회할 수 있다. 
• 메모리에 연속적으로 저장되지 않으므로 캐시 효율성이 좋지 않을 수 있다.

요약

Array는 연속적인 메모리에 고정 크기의 요소를 저장하는 선형 데이터 구조로 빠른 읽기와 쓰기 연산을 지원한다. LinkedList는 동적으로 크기를 조절할 수 있는 데이터 구조로 삽입과 삭제 연산이 효율적이지만 읽기가 상대적으로 느리다. 선택은 상황과 요구사항에 따라 다르며, 배열은 고정 크기를 필요로 할 때, LinkedList는 동적 크기 조절이 필요한 경우 사용된다.