[자료구조]Array & ArrayList &LInkedList

Array & ArrayList & LinkedList

빅오표기법, 시간복잡도와 공간복잡도

• 빅오 표기법 : ‘가장 영향을 많이 끼치는 높은 승수를 가진 항의 상수 인자를 빼고 나머지 항을 빼서 나타낸 복잡도표기법
• 공간 복잡도 : 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
• 시간 복잡도 : ‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계

Array(배열)

같은 타입의 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당되어 정해진 크기만큼 저장하는 자료구조

논리적 저장 순서와 물리적 저장 순서가 일치하고 index로 해당 element(원소)에 접근할 수 있다.

• 인덱스를 알고있다면 O(1)의 시간 복잡도로 원소에 random access 접근이 가능하다 .

• 삽입 또는 삭제 과정에서 해당 원소에 접근하여 작업을 완료한 뒤, shift(이동) 해야하므로 O(n)의 시간복잡도가 든다.

  • 삭제 기능에 대한 worst case = O(n)

• Array 특징

  • 고정된 저장 공간(fixed-size)

  • 순차적인 데이터 저장(order)

  • Array의 장점은 조회와 추가가 빠름. 따라서 조회를 자주 해야되는 작업에서는 Array 자료구조를 많이 사용

  • Array의 단점은 고정된 저장공간을 가지므로 선언시에 Array의 크기를 미리 정함.

    • 이는 메모리 낭비나 추가적인 overhead가 발생할 수 있다.

• 시간복잡도

  • 조회, 접근(access) : O(1)
  • 추가(append) : O(1)
  • 마지막 원소 삭제(delete) : O(1)
  • 삽입(insertion) : O(n) -> 모든 원소들의 인덱스를 shift하기 떄문
  • 삭제 (deletion) : O(n) -> 삽입과 마찬가지
  • 검색(search) : O(n) -> 모든 원소를 조회해야하므로

• 미리 예상하여 정해진 크기보다 더 많은 수의 데이터를 넘어서게 되면 어떻게 해결할 것인가?
  • 동적으로 배열의 크기를 늘리는 자료구조를 사용한다.
  • 기존 size보다 큰 Array를 선언하여 데이터를 옮긴다.
    • 모든 데이터를 옮기고 나서 기존 Array는 삭제.
  • -> Dynamic Array
    • 고정된 사이즈인 array의 한계점을 극복하고자 고안한 자료구조
    • 저장공간이 가득차면 resize를 하여 size를 조절한다.
    • resize : data를 계속 추가하다가 기존에 할당된 memory를 초과하게 되면, size를 늘린 array를 선언하고 그곳으로 모든 데이터를 옮김으로써 늘어난 크기의 size를 가진 array가 된다.
    • resize 방법
      1. doubling : 데이터를 추가하다가 크기를 초과하면 기존 array의 사이즈를 2배 높힌 큰 array를 선언하고 그곳으로 모든 데이터를 옮김 -> O(n)

append의 총 과정을 살펴보면 데이터를 마지막 인덱스에 추가하는(O(1))작업이 대다수,

size를 넘어설 때는 size를 두 배 늘리고 데이터를 일일이 옮기는 과정 (resize O(n))이 아주 가끔 발생합니다.

append의 전체적인 시간복잡도는 O(1), 좀 더 정확히 말하면 amortized O(1

가끔 발생하는 O(n)의 resize하는 시간을, 자주 발생하는 O(1)의 작업들이 분담해서 나눠 가짐으로써,

전체적으로 O(1)의 시간이 걸림.

LinkedList

Node라는 데이터와 다음 Node의 주소를 가리키는 구조체들로 이루어진 list

물리적인 메모리에서는 array와 다르게 비연속적으로 저장되지만, 자기자신의 다음 노드의 주소를 저장함으로써

논리적인 연속성을 가진 자료구조

연결리스트에는 단일, 다중 등 여러가지가 존재한다.

종류가 무엇이든, 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 되어있다.

단일은 뒤에 노드만 가리키고, 다중은 앞뒤 노드를 모두 가리키는 차이

• 시간복잡도 -> 자기 자신 다음의 주솟값을 저장함으로써 삭제와 삽입은 O(1)
  • 검색(search) -> O(n)
  • 삽입, 추가 -> O(1)
  • 삭제 -> O(1)
  • 그러나 원하는 원소를 찾고 삭제해야 하기 때문에 . 삭제 자체에는 O(1) 시간이 걸리지만, 조회하는데 O(n)이 든다
    • 결국 삽입과 삭제에 모두 O(n)이 든다.

Array와 LinkedList의 비교

• Array
  • 배열이며, 논리적 저장순서와 물리적 저장순서가 일치한다.
  • 특정 자료형들이 메모리 공간 상에서 연속적으로 이루어져 있다.
  • immutable하다.
  • 인덱스로 해당 원소에 접근할 수 있으며, 인덱스를 알고 있다면 O(1)의 시간 복잡도로 원소에 접근이 가능하다.
    • 즉, Random Access가 가능하다.
  • 삭제 또는 삽입 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤, shift해줘야 하므로 비용이 발생한다. O(n)
  • 메모리 공간 활용에 제약이 있다.
• LinkedList
  • 메모리 공간 상에서 각 노드들이 연속적으로 이루어져 있지 않고 흩어져 있으며, 각각의 노드가 자신의 다음 노드의 위치를 알고 있는 형태이다.
  • 데이터 검색 시 처음 노드부터 순회해야 한다. 이유는 논리적 저장 순서와 물리적 저장 순서가 다르기 때문이다. O(n)
  • 각 노드들이 메모리 공간 상의 어디에 위치하는지는 각각의 노드들만 알고 있고, 사용자는 제일 첫 번째 노드의 위치만 알고 있는 상태이다.
  • 어떤 원소를 삽입, 삭제 시 그 원소를 찾기 위해 O(n)의 시간이 발생하고 추가적으로 작업을 완료하는 시간까지 O(n)의 시간이 걸린다.
  • 결국, LinkedList는 검색과 삽입, 삭제 과정 모두 O(n)의 시간 복잡도를 갖는다.

• 따라서 얼마만큼의 데이터를 저장할지 미리 알고있고, 조회를 많이 한다면 Array를 사용하는 것이 유리.
• 반면에 몇개의 데이터를 저장할 지 불확실하고 삽입 삭제가 잦다면 Linked list를 사용하는 것이 유리.

• Array와 Linked List의 memory 할당은 언제 일어나며, 메모리의 어느 영역을 할당?
  • Array : 컴파일 단계에서 할당이 일어나고, 정적 메모리 할당, Stack memory영역에 할당
  • Linked List : 런타임 단계에서 노드가 추가될 때마다 메모리 할당이 일어나고 동적 메모리 할당. Heap 영역