2024 자료구조개론 & 알고리즘개론 정리 - 1. 배열과 링크드리스트

 

 

 

2024 자료구조개론 & 알고리즘개론 정리 - 1. 배열과 링크드리스트 

 

 

 

 

• 1. 배열과 링크드리스트 
• 2. Hash Table
• 3. Queue & Stack 
• 4. Tree & Graph 
• 5. Sorting 
• 6. Recursion 
• 7. 최적화 기법 (DP, Greedy, Divide & Conquer)

 

 

 

---

 

• list은 1) array list과 2) linked list로 나뉘어진다 
  • array list는 다시 1) static array와 2) dynamic list로 나뉘어진다 

 

 

array list 

 

 

• 1) Static array  
  • 정의 : 메모리 상에 1) 연속적으로 순차적으로 저장할 수 있으며, 2) 고정된 크기의 저장공간에 저장한다  
    • 위의 특징 때문에 3) Random Access (=Direct Access)가 가능하다 
      • n번째 데이터에 접근하기 위해 한 번의 연산을 하면 된다
      • 자료 저장에 최적화, 연속적/순차적으로 저장되어 있기 때문에 어떤 index에도 즉시 접근 가능
  • 장점 
    • 맨 뒤에 append와 lookup이 빠르다 -> 조회를 많이 해야 하는 작업에서 유리하다 
  • 단점 
    • 고정된 크기이기에 선언 이후에 size를 변경할 수 없다 

 

 

 

• 2) Dynamic array  
  • 정의 : 고정된 크기를 가진 Static array의 단점을 해결하기 위해, 자동적으로 resizing하는 array 
    • resizing 방법에는 대표적으로 Doubling 기법이 있다 - 기존에 할당된 메모리 크기를 넘어서개 되면 그 배열의 2배 큰 배열을 사용하게 된다 
  • 장점 
    • static array가 가진 장점들 - 1) 데이터 접근 - Random Access 2) 맨 뒤에 Append이 빠름
  • 단점 
    • (Linked List와 비교했을 때) 데이터를 맨 뒤가 아닌 곳에 추가하거나 삭제할 때 느리다
    • resize 시에 data를 계속 추가하다가 기존에 할당된 memory를 초과하게 되면, size를 늘린 배열을 선언하고 그곳으로 모든 데이터를 옮기는 방식을 사용하기 때문에 O(n)시간이 걸리게 된다 
      
      • 다만 분할 상환 시간 복잡도에 따라 resize 과정이 아주 가끔 일어나기 때문에 append의 전체적인 시간복잡도는 O(1)다 
    • Doubling 기법으로 인해 필요한 것 이상으로 memory 공간을 할당 받게 될 수 있다
  • 파이썬에서의 List가 Dynamic Array에 해당한다 

 

 

 

linked list 

 

 

• Linked List는 array list와 달리 1) 메모리 상에서 불연속적으로 저장되나, 2) 각각의 노드가 다음 노드의 주소값을 가리키고 있어 논리적으로 연속적인 형태를 가지게 된다 
• 장점
  • 맨 끝이 아닌 중간에 데이터를 추가하거나 삭제할 때 O(1)의 시간복잡도 
• 단점 
  • 오히려 맨 끝에 저장하게 될 때 시간 복잡도 높아짐 
  • 조회 시에 원하는 데이터를 찾기 위해서 모든 노드를 다 확인해야 하기에 O(n)의 시간복잡도를 가지게 된다
• 종류 ? 변형  
  • Circular Linked List : Linked List의 Tail이 다시 Head를 가리킴 
    • Single Linked List에 비해서 마지막에 원소 추가할 때 효율적임 
  • Double Linked List  -> 파이썬 모듈 collections의 deque이 이 double linked list로 구현되어있다 

 

 

 

Q. Array와 Linked List의 memory allocation은 언제 일어나며, 메모리의 어느 영역을 할당 받나요?


Array는 compile 단계에서 memory allocation이 일어납니다. 이를 Static Memory Allocation이라고 합니다. 이 경우 Stack memory영역에 할당됩니다.

Linked List의 경우 runtime 단계에서 새로운 node가 추가될 때마다 memory allocation이 일어납니다. 이를 Dynamic Memory Allocation이라고 부릅니다. Heap메모리 영역에 할당됩니다.


=> 파이썬에선 똑같지 않다!!!!!!!!!!!!! (https://asidefine.tistory.com/255)

파이썬에서는 다음과 같이 숫자, bool, string 자료형은 기본자료형, List나 dictionary, 함수와 같은 것들은 복합자료형에 해당이 된다.

기본 자료형은 크기가 작고 고정되어 있어 상자(스택)에 넣어 차곡차곡 보관하고,
복합 자료형은 크기가 정해져 있지 않은 복잡한 자료로 다른 창고(힙)에 넣고 보관하고 창고 위치를 스택에 보관한다


함수는 복합 자료형이기 때문에 힙(heap)에 저장된다.
함수를 호출할 때마다 스택(stack)이 새로 생성되고, 함수 호출이 완료되면 스택(stack)은 사라진다. 

 

동적 배열: deque는 더블 링크드 리스트의 노드를 담는 여러 개의 작은 동적 배열로 구성됩니다. 각 배열 블록은 특정 수의 요소를 포함할 수 있으며, 블록들은 서로 링크로 연결되어 있습니다. 이렇게 구현함으로써 deque는 링크드 리스트보다 메모리를 효율적으로 사용하며 캐시 친화적인 접근을 유지할 수 있습니다.

메모리 사용 최적화: deque의 이러한 구현은 메모리 오버헤드를 줄이고, 데이터의 연속성을 유지하여 성능을 개선합니다. 더블 링크드 리스트와 달리 각 노드가 하나의 데이터만 가지고 있는 대신, 블록 단위로 여러 데이터를 관리함으로써 포인터 오버헤드가 줄어듭니다.

자동 크기 조정: 아이템이 추가되어 현재의 배열 블록들이 포화 상태에 이르면, deque는 자동으로 새로운 블록을 생성하여 용량을 확장합니다. 마찬가지로, 아이템이 제거되어 블록들이 충분히 비어 있을 때는 불필요한 블록을 해제하여 메모리 사용을 최적화합니다.

스레드 안전성: deque는 스레드 안전하지 않습니다. 따라서 멀티스레딩 환경에서 deque를 사용할 경우, 적절한 락(lock)을 사용하여 동시성을 관리해야 합니다

 

 

---