[CS/자료구조] 배열, 링크드리스트

메모리할당 및 탐색

• 배열: 연속적인 메모리 블록에 요소들을 저장. 인덱스로 요소들에 접근: O(1)
• 링크드리스트: 각 요소들이 독립적으로 메모리에 할당, 다음 요소를 가리키는 포인터로 연결. 인덱스로 요소들에 접근하는데 O(n) 시간 소요.

크기조절 및 추가/삭제

• 배열: 크기가 고정되어 있어, 변경이 어려움. 새로운 배열을 생성하고 기존 데이터를 복사함. 중간에 위치한 요소가 변경될 경우, 해당 위치의 요소들을 이동시켜야함.
• 링크드리스트: 동적으로 크기 조절 가능. 새로운 요소 추가/삭제 시 메모리 재할당 없이 포인터만 수정하여가능.

메모리공간

• 배열: 요소들을 연속적으로 저장하여 저장공간 낭비가 없음
• 링크드리스트: 포인터로 요소들을 연결하기 위한 포인터 공간이 필요

Reference
: Chat-GPT:3.5