Array

정의

인덱스 와 이에 대응하는 데이터 들로 이루어진 자료구조.
같은 종류의 데이터들이 순차적으로 저장되어, 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어있는 상대적인 위치가 된다. - wikipedia

개념

• 메모리상에 데이터가 연속적으로 저장된 선형 자료구조
  • 선형 자료구조 : 원소들을 순서대로 나열한 자료구조
  • 순차 리스트 : 원소들이 실제 메모리상 시작위치부터 끝 위치까지 순차적으로 저장된 것
• 기본주소와 각 원소의 인덱스만으로 데이터에 접근할 수 있다.(Random Access)

특징

• 같은 타입의 변수들로 이루어져 있다.
• 논리적 저장순서와 물리적 저장순서가 일치한다
• 고정된 크기를 가진다 -> 메모리의 낭비가 발생할 수 있음
• 오버헤드가 거의 없다
• 메모리를 미리 확보해야 한다
• Cache hit rate가 높다
  • 배열은 데이터가 연속된 메모리공간에 저장되므로 공간 지역성이 높기 때문

동작

• 접근 : 배열의 시작주소와 인덱스로 원소에 접근한다. (Random Access)
  • O(1)
• 삽입, 삭제 : 인덱스로 접근한 위치에 원소를 삽입하거나 삭제하면 그 뒤에 있는 원소들을 모두 앞이나 뒤로 Shift함
  • O(n)

활용

• 가장 기본적인 자료구조로, 같은 성질을 가진 데이터를 모아서 관리할 때 사용함

Linked List

정의

각 노드가 데이터 와 포인터 를 가지고 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료구조. - wikipedia

개념

• 메모리 상에 데이터가 연속적으로 저장되지 않는 선형 자료구조.(순차 리스트가 아님)
• 각 노드의 포인터를 통해 이전 혹은 다음 노드로 연결

특징

• 크기가 가변적이다 -> 메모리의 낭비가 없음
• 논리적 저장 순서와 물리적 저장순서가 다르다
• 이전 노드의 주소를 저장해야하므로 오버헤드가 있다.
• Cache hit rate가 낮다
  • 연결리스트는 데이터가 연속된 메모리공간에 저장되지 않으므로 공간 지역성이 낮음

동작

• 접근 : 첫번째 원소부터 순차적으로 탐색하여 접근(Sequential Access)
  • O(n)
• 삽입, 삭제 : 삽입의 경우 노드를 새로 만들어 새로운 노드의 포인터를 삽입할 위치의 노드 주소로, 다음 노드의 포인터를 새로운 노드의 주소로 연결한다. 삭제의 경우 삭제할 노드의 앞, 뒤 노드의 포인터를 서로 연결한다.
  • O(n) : 포인터를 연결하는 작업은 O(1)이지만, 삽입/삭제할 노드를 찾는 작업에 O(n)이 걸림

종류

• 단순 연결 리스트 : 각 노드당 하나의 포인터가 다음 노드의 위치를 가르킴
• 이중 연결 리스트 : 각 노드당 두개의 포인터가 이전 노드와 다음 노드의 위치를 가르킴
• 원형 연결 리스트 : 단순 연결 리스트에 마지막 노드의 포인터가 첫번째 노드의 위치를 가르킴

활용

• 배열에 비해 삽입/삭제가 용이하지만 탐색속도가 떨어지므로 탐색을 자주하면 배열, 삽입, 삭제를 자주하면 연결리스트를 사용하는 것이 유리하다.