참고 자료
[BoostCourse - cs50 - linked list] : https://www.boostcourse.org/cs112
[초보몽키의 개발공부로그] Array와 리스트 : https://wayhome25.github.io/cs/2017/04/17/cs-18-1/
[Java의 LinkedList와 ArrayList 에 대한 비교] : https://www.holaxprogramming.com/2014/02/12/java-list-interface/
[에러지우개] Array vs ArrayList : https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Array-vs-ArrayList
#List
이번에 공부할 자료구조는 List이다. 배열은 정적이기 때문에 크기를 재조정할 수 없어 기존 배열에 데이터를 추가/삭제하는 것이 불가능한 한계가 있었다. 그렇다면 정적인 자료구조(즉, 데이터를 추가/삭제 할 수 있는 자료구조)는 없을까?
당연히 있다. 이번에 다룰 List는 정적인 자료구조이다. 그럼 본격적으로 List에 대해 알아보자.
1. 리스트란?
리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재라는 장점을 취한 자료구조이다. 리스트 자료구조의 핵심은 엘리먼트들 간의 순서이다. 그렇기 때문에 리스트를 시퀀스(sequence)라고도 부른다. 즉, 리스트는 순서가 있는 데이터의 모임이다.
리스트 특징
- 배열의 인덱스는 값에 대한 주민번호같은 유일무이한 식별자인 반면, 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가진다. 그 이유는 데이터의 위치가 언제든 바뀔 수 있기 때문이다.
- 빈 엘리먼트를 허용하지 않는다. 리스트에서 데이터를 삭제하면 그 공간을 다시 채운다. (배열은 삭제된 데이터의 빈공간을 그대로 둔다.) 이를 통해 데이터를 추가/삭제 시 메모리를 효율적으로 사용가능하다.
- 순차성을 보장하지 못하기 때문에 spatial locality 보장이 되지 않아서 cash hit가 어렵다.
- 데이터 갯수가 확실하게 정해져 있고, 자주 사용된다면 array가 더 효율적이다.
- 리스트에 대한 효용은 어떤 언어를 사용하느냐에 따라서 달라진다. 많은 언어에서 리스트를 기본적으로 지원하기 때문에 제공하는 리스트를 쓰는 일이 많다.
리스트를 구현할 때 핵심 기능을 정리하면 다음과 같다.
- 처음, 끝, 중간에 엘리먼트를 추가/삭제하는 기능
- 리스트에 데이터가 있는지를 체크하는 기능
- 리스트의 모든 데이터에 접근할 수 있는 기능
cf > 캐시(Cache)란?
Cache란 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 장소를 가리킨다. 캐시는 저장 공간이 작고 비용이 비싼 대신 빠른 성능을 제공한다. (캐시에 대한 내용은 다른 게시물로 다루겠다.)
1. cache locality: 운영체제에선 물리적으로 근접한 위치의 데이터가 주로 활용되기 때문에 미리 캐쉬에 넣어둠으로써 CPU의 성능을 향상시킨다. 배열은 물리적으로 연속된 공간에 데이터를 저장하기 때문에 이러한 locality를 잘 활용할 수 있다.
2. cache hit: 1과 같이 지역성을 활용하기 위해 캐쉬에 저장해놓은 메모리에 CPU가 참조하고자 하는 메모리가 있다면 cahce hit, 캐쉬 적중이라고 한다. 반대의 개념은 cache miss.
3. spatial locality: 1에서 설명한 지역성은 시간 지역성(Temporal locality)과 공간 지역성(Spatial Locality)으로 나뉜다. 시간 지역성(Temporal locality)이란 가장 최근에 읽어온 data는 다시 읽어올 때도 빠르게 access할 수 있다는 뜻이다. for나 while 같은 반복문에 사용하는 조건 변수처럼 한번 참조된 데이터는 잠시 후에 또 참조될 가능성이 높다. 공간 지역성이란 A[0], A[1]과 같은 데이터 배열에 연속으로 접근할 때 참조된 데이터 근처에 있는 데이터가 잠시 후에 사용될 가능성이 높다는 것이다.
[출처]: [Deep learning/Machine Learning/CS 공부기록] - 배열, 연결 리스트 , [MangKyu's Diary] - 캐시란?
언어별 지원하는 리스트 정리
1. C : 리스트 지원 x 배열만 지원한다. 따라서 리스트를 사용하려면 직접 만들거나 라이브러리를 사용해야 한다.
2. Python : 기본적으로 리스트를 제공, 배열은 제공하지 않는다. 리스트를 배열처럼 사용함. C의 array 보다 메모리를 더 많이 필요로 함.
3. Java : 자바는 배열과 리스트를 모두 지원한다. ArrayList, LinkedList 두 개의 리스트를 지원한다. 자료구조에 대한 이해가 충분하다면 효율적인 자료구조를 선택 가능하다.
이번에는 Java 에서 제공하는 ArrayList / Linked List 에 대해 알아보자. 리스트라고 다 같은 리스트가 아니다. 리스트의 핵심 기능만 가지면 리스트이기 때문에 이를 구현하는 방법은 많다. 그 중에서 ArrayList / Linked List 을 알아보자.
2. ArrayList
ArrayList는 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해 임시 배열을 생성해 데이터를 복사 하는 방법을 사용한다.
이는 배열에서 다룬 추가 / 삭제 코드의 방법과 동일한 방법이다. ArrayList는 대량의 자료를 추가/ 삭제 하는 경우에 기존 배열을 복사하기 떄문에 성능 저하를 일으킬 수 있다. 하지만 데이터는 인덱스를 가지고 있기 때문에 한 번에 참조가 가능해 데이터의 검색에 유리한 규현체이다.
즉, ArrayList는 Array 를 이용해 가변적으로 만드는 작업을 자동으로 처리해주는 것이다.
ArrayList 특징
- 기본적으로 ArrayList의 Default는 10개의 공간을 가진 배열로 시작한다. (단, 지연 초기화를 이용해 생성하면 0개의 사이즈로 시작)
- 배열을 이용한다면 미리 공간을 결정해야한다. 데이터를 삽입하는 경우 매번 배열을 복사하는 것이 비효율적이므로 어느정도 여유 공간을 만들어 둔다. ArrayList는 배열의 size를 저장하는 capacity 변수를 가지고 있다. capacity를 넘는 객체가 들어오면, 배열 크기를 1.5배 증가시킨다.
- ArrayList는 오직 객체만을 데이터 요소로 가질 수 있다. int 형인 13을 arrayList에 추가한다고 가정하면, 내부적으로 AutoBoxing(primitive type 을 타입에 상응하는 wrapper class로 변환해주는 것)을 통해 int -> Integer 객체로 변환해 ArrayList에 저장하게 된다.
- ArrayList는 iterator를 사용해 ArrayList를 순회할 수 있다.
- 자료구조의 크기 값을 얻을 때는 size() 함수를 이용한다. (배열은 length 변수)
- 단일 차원만 가능 (배열은 다차원 가능)
3. Linked List
Linked List는 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다고 보면 된다. (* 노드 : 데이터를 보관하는 필드 + 다음 노드와의 연결 고리 역할을 하는 포인터(주소)로 이루어진다.) 즉, Linked List는 '노드'를 연결해서 만드는 리스트이다.
Linked List는 데이터가 늘어날 때마다 노드를 만들어 이어주면 된다. 그래서 배열과 다르게 데이터를 메모상에 연속해서 저장할 필요가 없다.(노드를 이용해 메모리 어디서든 저장해서 연결함) 이러한 구조이기 때문에 ArrayList에 비해 데이터의 추가, 삭제 시에 유리하다.
하지만 이런 유동적인 구조는 대가가 따른다. 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능하다. 연결 리스트에 값을 추가하거나 검색하는 경우를 생각해보자.
이를 실행하기 위해서는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야한다. 따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이다. ArrayList의 경우 임의 접근이 가능하기 때문에 데이터를 검색하는데 (정렬되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요된다.
4. 정리
위 그림으로 ArrayList 와 Linked List 를 언제 사용해야 할 지 정리할 수 있다. ArrayList는 데이터의 검색 성능이 중요할 때, Linked List는 데이터를 추가 /삭제하는 성능이 중요할 때 사용하면 된다.
리스트 개념 정리 완료.
<추가적으로 공부할 내용들>
linked list 의 다양한 구현 방법
(더블 링크드 리스트, 환형 링크드 리스트)
캐시
