[CS - 자료구조] 배열 & 연결 리스트 (Array & Linked List)

Array

개념

• 연관된 data를 메모리상에 연속적, 순차적으로 미리 할당된 크기만큼 저장하는 자료구조

 

operation의 time plexity

• 조회(lookup), 마지막 인덱스에 추가(append), 삭제 : O(1)
  • 이유 random access (즉시 접근)
  • 설명 Array는 데이터가 연속적으로 저장되기 때문에, 한 번의 계산으로 접근 가능
• 삽입(insert), 삭제(delete) : O(n)
  • 이유 Array의 연속적, 순차적인 특징
  • 설명 데이터가 연속적, 순차적으로 붙어있어야 하기 때문에, 변경이 생긴 곳 뒤에 있는 데이터들은 일일이 자리를 밀거나 땡겨야 함
• 탐색(search) : O(n)
  • 이유 주소값 하나씩 돌면서 찾는 데이터가 어떤 주소값에 있는지 일일이 확인해야 함

 

장점

• 조회(lookup), 추가(append)가 빠름 (O(1))
  • → 조회, 추가를 자주 하는 작업에서는 Array가 효율적

 

단점 

• fixed-size 라서 크기를 미리 정해야 함
  • → 메모리 낭비, 추가적인 overhead 발생 가능
  • ex 100 size의 Array 생성
    1. 데이터가 10개인 상황 → 90개의 메모리가 낭비되고 있다 : 메모리 낭비
    2. 데이터가 150개인 상황 → 150 size (또는 그 이상의) Array 새로 생성하고, 데이터 일일이 옮기고, 기존 Array 삭제 : overhead 발생

 

 

Dynamic Array

개념

• 연관된 data를 메모리상에 연속적, 순차적으로 미리 할당된 만큼 저장하는 자료구조인데,
• data를 추가하는 상황에서 (append) fixed-size보다 커졌을 때 resize를 통해 유동적으로 크기를 조절하여 저장하는 자료구조

 

resize 흐름 예시

• [상황] fixed-size가 4인 배열 [1,2,3,4]에 5를 append하려는 상황
  1. 더 큰 size의 Array 생성
  2. 기존 Array에서 데이터 하나씩 다 옮기기
  3. 기존 Array 제거
  4. 새 Array에 5 추가

 

Doubling

• 더 큰 size의 Array를 생성할 때 두 배 큰 Array를 생성하는 방식
• resize의 대표적인 방법
• 흐름
  1. 데이터를 추가 (append, O(1)) 하다가 메모리를 초과하는 상황 발생
  2. 두 배 큰 size의 Array 선언
  3. 일일이 데이터 옮김
  4. n개의 data → O(n)
  5.  

 

분할 상환 시간복잡도, Amortized time complexity

• 단편적으로 얘기해서, Dynamic Array의 append 시간복잡도는 무엇?
• 결론적으로 얘기해서, amortized O(1)
  • 대부분 O(1)인 경우가 많음
  • 가끔 메모리를 초과해서 resize하고 데이터 옮기는 상황 발생 (O(n))
• 왜 그냥 O(1)이 아닌, amortized O(1) ?
  • 가끔 발생하는 O(n)의 작업을
  • 자주 발생하는 O(1)의 작업이 분담해서 나눠 가짐
  • 이게 분할 상환 시간복잡도이고, amortized O(1)

 

Q) Dynamic Array를 Linked List와 비교했을 때 장, 단점 ?

• 장점
  • 조회(lookup), 추가(append)가 빠르다 : O(1)
• 단점
  • 추가(insert), 삭제(delete)가 느리다 : O(n)
  • resize의 시간이 예상치 못하게 오래 걸리는 경우가 있고
  • 이 때문에, 한번할 때 넉넉한 메모리 크기로 resize 한다 → 메모리 낭비 발생

 

 

Linked List

개념

• data를 [ data & 다음 Node의 address ] 로 이루어진 Node 라는 구조체로 저장하는 자료구조
• 메모리상에서 물리적으로는 비연속적으로 저장되어 있지만, 각 Node가 다음 Node의 address를 가리키기 때문에 논리적 연속성을 가짐
• 예시
  • Array = [a,b,c,d]
  • head → a|next → b|next → c|next → d|next → null
  • 메모리상에선 뒤죽박죽으로, 붙어있지도 않게 저장되어 있음

 

논리적 연속성

• 각 Node들이 next address 정보를 가짐 → 논리적 연속성 보장
• 메모리상에 꼭 붙어있거나 순서대로 저장되지 않아도 됨
  • → 메모리 사용이 자유로움 & 효율적
  • → 하지만, 각 Node당 data와 next address를 들고 있기 때문에 data 하나당 차지하는 메모리가 더 큼
• Array : 물리적 연속성 → 메모리상에 순차적으로 저장하는 방법으로 연속성 유지

 

데이터 삽입(insert), 삭제(delete)

• 시간복잡도 : O(1)
• 이유 삽입 또는 삭제하려는 위치를 가리키는 Node의 next address만 수정하면 됨
• 삽입(insert)
  • 상황 [a,b,c,d]를 [a,b,10,c,d]로 만들고 싶음
  • 방법
    • 기존 : a | next → b | next → c | next → d | next
    • 변경 : a | next → b | next → 10 | next → c | next → d | next
• 삭제(delete)
  • 상황 [a,b,c,d]를 [a,c,d]로 만들고 싶음
  • 방법
    • 기존 : a | next → b | next → c | next → d | next
    • 변경 : a | next → c | next → d | next

 

데이터 조회, 탐색

• 시간복잡도 : O(n)
• 이유 Linked List는 데이터를 연속적, 순차적으로 저장하지 않음
• 설명 random access를 사용할 수 없음. next address를 하나씩 타고 가는 방법밖에 없음

 

 

Array vs Linked List

 

Q) Array와 Linked List의 memory allocation은 언제, 어디서 발생?

• Array
  • 시기 컴파일 단계에서 메모리를 할당하고, 이를 정적 메모리 할당 (static memory allocation)이라고 함
  • 장소 스택 메모리에 저장됨 (정적 메모리 담당하는 곳)
• Linked List
  • 시기 런타임 단계에서 메모리를 할당하고, 이를 동적 메모리 할당 (dynamic memory allocation)이라고 함
  • 장소 힙 메모리에 저장됨 (동적 메모리 담당하는 곳)