리스트 (1) 썸네일형 리스트형 배열과 리스트 배열(Array) 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 즉, 논리적 저장 순서와 물리적 저장 순서가 일치한 형태로 구성된 자료구조 ⇒ 연속적인 메모리 할당 ⇒ 인덱스 사용 가능 시간복잡도 삭제: 빈자리가 남게되어 메모리가 낭비 ⇒ 마지막 값 삭제할 때만 O(1)이고 그 외에는 O(N) 삽입: 연속적인 형태 유지를 위해 shift 연산이 필요 ⇒ O(N) (맨 뒤에 추가할 것이고 배열에 공간이 남아 있으면 예외적으로 O(1)) 검색, 수정: 인덱스를 통한 검색과 수정이 용이 ⇒ O(1) 리스트(Linked List) 불연속적인 메모리 공간에 저장하므로 크기 제한에서 자유로움 노드 간에 연결을 통해 리스트로 구현된 객체 시간복잡도 삭제: 삭제하려는 데이터의 위치가 맨 앞이면 O(1), 그 외에.. 이전 1 다음