알고리즘 뿌시기 두번째-1 (Array와 LinkedList)

오늘은 알고리즘 강의 2주차이다.!

오늘은 두가지의 강의가 있는데, Array와 LinkedList와 이진 탐색과 재귀 함수 이다..!

일단 첫번째로
ArrayList와 LinkedList에 대해 정리해보려고 한다.

Array이란?

Array(배열)이란 크기가 정해진 데이터의 공간이다.

Array의 특징

• 한 번 정해지면 바꿀 수 없다.
• 원소의 순서는 0부터 시작하며 이를 인덱스라고 부른다.
• 즉시 접근이 가능하다. (상수 시간 내에 접근이 가능하다)
  ㄴ$O(1)$ 만에 접근이 가능하다.
• 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야함.
  ㄴ최악의 경우 배열의 길이 N만큼 옮겨야 하므로 $O(N)$이 걸린다.
  ㄴ원소를 삽입/삭제 할 경우 비효율적인 자료구조이다.

예를 들어,
조카의 생일파티를 하려고 한다.

조카가 옛날에 들었던 기억으로는 친구 두명과 삼총사로 친하다고 해서 접시를 세 개만 샀다.

근데 웬 걸, 생일파티하는 날에 전학온 친구와 친해져 네명이서 사총사를 한다며 집으로 왔다.

상황이 곤란해진다..
위와 같이 배열은 한 번 정해지면 바꿀 수 없다.

LinkedList란?

List란 크기가 정해지지 않은 데이터의 공간이다.

LinkedList의 특징

• 연결 고리(포인터)로 이어주면 자유자재로 늘어날 수 있다.
• 특정 원소에 접근히려면 연결 고리를 따라 탐색해야 한다.
  ㄴ최악의 경우, 모든 원소(노드)를 탐색해야 하므로 $O(N)$의 시간복잡도를 가진다.
• 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다.
  ㄴ원소 삽입/삭제를 $O(1)$의 시간 복잡도 안에 할 수 있다.

Array VS LinkedList

경우	Array	LinkedList
특정 원소 조회	$O(1)$	$O(N)$
중간에 삽입 삭제	$O(N)$	$O(1)$
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용하는 것이 좋다	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다

파이썬의 배열은 list일까, array일까?

• array오 구현되어있지만, 동적 배열을 사용해 배열의 길이가 늘어나도 $O(1)$의 시간 복잡도가 걸리도록 설계되었다.

• 파이썬의 배열은 list로도 쓸 수 있고, array로도 쓸 수 있게 만든 효율적인 자료구조이다.

• 참고자료 : https://stackoverflow.com/questions/5932328/internals-of-python-list-access-and-resizing-runtimes/5932364#5932364

• $O(1)$의 시간 복잡도가 걸리지만 실제 array보다는 실 시간은 오래 걸린다고 볼 수 있다.