배열 (Array)
같은 타입의 데이터를 나열한 선형 자료구조
연속된 메모리 공간에 순차적으로 저장
배열의 크기는 고정. 선언할 때 배열의 크기를 정하고, 변경할 수 없다.
시간복잡도
- 삽입/삭제
- 배열의 맨 앞에 삽입 삭제하는 경우 : O(n)
- 배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)
- 배열 중간에 삽입/삭제하는 경우 : O(n)
- 탐색
- O(1)
장점
- 인덱스를 가지고 있어 바로 접근 가능 - O(1)
- 연속된 메모리 공간에 존재하기 때문에 관리가 편하다.
단점
- 삽입과 삭제가 어렵고 오래 걸린다.
- 원소를 삽입하거나 삭제할 경우, 해당 원소 이후의 모든 원소들을 한칸씩 밀거나 당겨야 한다.
- 연속된 메모리 공간에 저장되기 때문
- 배열의 크기를 바꿀 수 없다.
- 배열은 처음 생성할 때 크기를 결정하고 고정
- 크기를 변경하기 위해서는 원하는 크기의 새로운 배열을 생성한뒤 값을 복사해야 함.
- 연속된 메모리 공간을 사용하기 때문에 공간낭비가 발생
- 중간에 데이터가 삭제되면 공간 낭비가 발생할 수 있음. 또, 처음에 배열 크기를 100으로 생성했는데 10정도 밖에 쓰지 않으면 나머지 공간은 빈 공간으로 낭비가 발생함
- 연속적인 메모리 할당이 필요하다
- 메모리 공간을 많이 사용하게 될 수 있다.
언제 사용할까
- 데이터의 개수가 확실하게 정해져 있을 때
- 삽입/삭제가 적을 때
- 검색을 해야할 때
리스트 (Linked List)
- 데이터를 순차적으로 저장하는 선형 자료구조
- 불연속적 메모리 공간에 저장
- 노드를 연결하여 만든 리스트
첫 번째 노드를 헤드, 마지막 노드를 테일이라고 함
각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어짐
- 크기가 고정되어 있지 않고, 새로운 요소를 크기가 정해져 있지 않으므로 새로운 요소를 추가할 때 크게 제한에서 자유롭다.
- 인덱스 접근이 불가능하다.
시간 복잡도
- 삽입
- 리스트의 맨 앞/뒤에 삽입 or 삭제 : O(1)
- 리스트의 중간에 삽입 or 삭제: O(n)
- 탐색
- O(n)
장점
- 삽입과 삭제가 용이
- 포인터로 연결되어 있어 포인터가 가리키는 노드만 변경해주면 됨.
- 크기가 정해져 있지 않고 동적으로 생성
- 연속적인 메모리 할당이 필요하지 않다
- 사용한 메모리 재사용 가능
단점
- 삽입과 삭제가 빈번할 때 성능이 좋지 않음.
- 검색을 자주 하지 않을 때
Uploaded by Notion2Tistory v1.1.0