(2022-11-21) 배열과 리스트
알고리즘 문제를 풀다가 배열과 리스트에 대해 헷갈려서 아직 개념을 확실히 알지 못한다고 판단되어 다시 공부할겸 적게 되었다.
배열(Array)
- 데이터가 많아지고 그룹 관리의 필요에 따라 배열을 사용한다.
- 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인(논리적 저장 순서와 물리적 저장 순서가 일치) 형태로 구성된 자료구조
- 인덱스에 따라 값을 유지하므로 원소가 삭제되어도 빈자리가 남게되어 메모리가 낭비된다.
- 처음 크기를 10으로 지정한다면 5개의 데이터만 저장하더라도 실제 배열의 크기는 10이다.
- 인덱스(index) : 각 원소의 번호로 0번부터 시작하며, 해당 원소에 접근한다.
- 데이터 갯수가 확실하게 정해져 있고, 접근이 빈번한 경우 배열이 효율적이다.
- c-ache hit 가능성이 커져 성능에 큰 도움이 된다.
- ca-che hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우
- 고정이고 연속적인 만큼 인덱스로 random access가 가능하다.
- 접근, 수정 O(1)으로 빠르게 조회가 가능하다.
- 하지만 삽입과 삭제의 경우 연속적인 형태 유지를 위해 shift 연산을 해야하므로 O(n)이 된다.
리스트(List)
- 배열의 문제점을 해결하기 위한 자료구조
- 빈틈없는 데이터의 적재라는 장점을 가진다.
- 원소를 삭제했을 때 삭제된 데이터 뒤 원소로 빈틈없이 연속적으로 위치시킨다.
- 리스트의 핵심은 원소들 간의 순서로 순서가 있는 데이터의 모임이 리스트이며 리스트를 다른 이름으로 시퀀스(sequence)라고도 부른다.
- 배열에서 인덱스는 유일무이한 식별자이지만 리스트에서는 몇 번째 데이터인지 정도의 의미를 가진다.
- 빈 엘리먼트는 허용하지 않는다.
- 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아 cash hit가 어렵다.
- spacial locality : 프로그램 실행 시 접근하는 메모리 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다는 프로그램 성격 표현
| 저장 방식 | 크기 할당 | 속도 | |
| Array(배열) | 정해진 공간이 있고, 그 모든 곳의 식별자(인덱스)가 존재 ex) str[i] |
객체생성시 크기 할당 필수 ex) char[] c = new char[3] |
삽입/삭제: 느림 데이터조회: 빠름 |
| List(리스트) | 식별자(인덱스)가 없음, 앞의 요소가 삭제되면 새로 추가되는 요소가 그 공간에 저장될 수 있음 |
크기 할당 필요X (자바에선 자동으로 1.5배씩 늘어남) |
삽입/삭제: 빠름 데이터조회: 느림 |
배열의 크기는 length를 쓰고
리스트의 크기는 size를 써야함