[CS/Data Structure] 2. 배열과 연결리스트 (Array & Linked List)

배열

배열의 특징

1. 대표적인 선형 자료구조
2. 가장 기본적인 자료구조
3. 메모리에 연속적으로 데이터를 저장하는 자료구조로, 논리적 저장순서와 = 물리적 저장순서(일치)
4. 탐색 O(1), 삽입/삭제 O(N) → 접근이 용이하며 데이터 삽입및 삭제가 어렵다.
5. → 논리적 저장순서 = 물리적 저장순서이기에, 인덱스로 해당 원소에 접근할 수 있으므로 탐색시 O(1)로 접근 가능하다 ⇒ 즉, Random Access 가 가능하다는 장점이 있다
6. 크기 고정적
7. Cache locality(정의 링크) 가 좋아 Cache Hit 가능성이 크다.

연결리스트

연결리스트의 특징

1. 배열과 동일한 선형 데이터 자료구조이나, 연속적인 메모리 위치에 저장되지 않는다.
   (메모리가 불연속적으로 배치된 선형 자료구조)
   • 연결 리스트에서 서로 연결된 원소(element)들은 노드(node) 혹은 정점(vertex)라고 부름
2. 배열에서 삽입/삭제가 어려웠던 문제를 해결하기 위한 자료구조
   → 삽입/삭제 연산이 용이
3. 각 노드는 (1) 데이터 필드와, (2) 다음 노드에 대한 참조를 포함하는 노드로 구성된다
   → 자료의 주소 값으로 노드 간 서로 연결된다
   → 각각의 원소들은 자기 자신 다음에 어떤 원소인지만 기억하고 있다 (포인터를 사용해 연결됨)
   → 원소와 원소간의 연결(link)을 이용해서 리스트를 구현한다
   → 이 부분만 바꿔주면 삽입/삭제을 O(1)만에 해결할 수 있다
4. 탐색 O(n), 삽입/삭제 O(n)
   • 삽입과 삭제할 원소를 찾는게 O(n)이 걸리기 때문에 결과적으로 삽입/삭제도 O(n)이 걸리게 되는 것이다.

배열과 연결리스트의 비교

차이점

1. 저장방식
   • 배열과 다르게 연결리스트는 그 위치가 흩어져 있기 떄문에, 서로 연결되어있어야만하고, 이 과정에서 연결이라는 개념이 사용된다.
2. 검색속도 (배열>연결리스트)
   • 배열 → 인덱스 값을 미리 알고 있는 경우, 데이터에 신속한 접근 가능
   • 연결리스트 → 검색 속도가 느림
     • Random Access 불가 → 탐색하는 경우 1번째 노드부터 순차적으로 요소에 액세스 해야함
       (이진 검색 수행 불가)
       → 배열과 달리 논리적 저장순서와 물리적 저장순서가 일치하지 않기 때문
3. 저장공간 크기의 유동성 (배열 < 연결리스트)
   • 배열 → 배열의 크기가 고정되어 있어, 미리 요소의 수에 대해 할당을 받아야 함
   • 연결리스트 → 동적 크기
4. 저장공간 효율성 (배열 > 연결리스트)
   • 배열 → 데이터의 수만큼만 차지
   • 연결리스트 → 저장공간 효율이 높지 않음 → 연결정보를 저장하는 저장공간이 별도로 필요하기 때문.
5. 삽입과 삭제 연산 (배열 < 연결리스트)
   • 배열 → 새로운 요소를 삽입하는 것은 큰 비용 (공간을 만들고, 기존 요소들을 전부 이동시켜야함
     → 오버 헤드 발생 가능성)
   • 연결리스트 → 삽입/삭제가 용이

사용 상황

• 연산 중 차지하는 연산 비율에 따라 결정
• 배열 → 데이터 접근이 많은 경우
• 연결리스트 → 삽입/삭제가 많은 경우

연결리스트의 종류

1. 단방향 연결리스트

단방향 연결리스트 데이터

• 일반적으로 연결리스트(Linked List)로 부르는 것으로, 배열과의 차이에서 지속적으로 언급해온것을 의미
• 연결 리스트는 연속되지 않은 메모리에 저장된 데이터들을 연결시켜 놓은 것 이기때문에,
  data에 내 **데이터 값을 저장**하고, next에 다음 노드의 주소값을 저장
  → 이 네모 2칸을 노드(node)라고 부름

2. 양방향 연결리스트

• 단방향 연결리스트의 탐색의 단점을 극복하고자 나온 자료구조
  • 단방향 연결리스트는 순차 탐색해야 하므로, 효율성이 매우 떨어짐

양방향 연결리스트

• 가장 첫 노드를 가르키는 head뿐만 아니라, 가장 마지막 노드를 가르키는 tail도 가지고 있어서, 양방향 접근이 가능

Array 관점에서 ArrayList와 LinkedList

• 해당 비교는 Java 기준. 자료구조관점에서만 비교했을 때이다.

• 핵심 포인트는, Array는 random access , linked list는 sequential access 기 때문에 시간복잡도에서 차이가 난다는 점
  • Array는 index로 빠르게 값을 찾는 것이 가능함
  • LinkedList는 데이터의 삽입 및 삭제가 빠름
  • ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림

ArrayList vs LinkedList

• 사용 상황
  • 결국엔 ArrayList도 배열과 비슷하다.
  • 자주 탐색 → ArrayList (검색에 유리)
  • 자주 삽입/삭제 → LinkedList
  • 이유 : ArrayList는 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해 아래와 같이 임시 배열을 생성해 데이터를 복사하는 방법을 사용 하고 있기 때문에 삽입 삭제시 많은 복사가 일어나기 때문.