[알고리즘] 배열(array), 연결 리스트(linked list)

👋 들어가기전

• 알고리즘 전반적인 지식을 다음 페이지에 모아두고 있습니다. 필요시 확인하세요~

2022.07.26 - [알고리즘] - [알고리즘] 알고리즘 다수의 링크

[알고리즘] 알고리즘 다수의 링크

 

🚨 급한사람!!  이거만 보세요

• 배열(array)이란?
  • 데이터를 묶어 놓는 집합체
  • random access(direct access)를 제공 하는 자료구조이다.
    • index를 알고 있다면 O(1)시간에 데이터에 접근 가능하다.
  • 메모리에 연속적으로 조각이 잡힌다.
• 배열을 사용해야 하는 이유, 하지만..
  • random access!!, 임의 접근은 이진탐색(binary search) 알고리즘을 사용하기 위해서 필요하다.
    • (이진탐색 하나만으로 사용할 이유는 충분하다)
  • 검색, 삽입, 삭제는 O(n)으로 성능이 좋지 않다.

 

• 연결 리스트(linked list)란?
  • 참조를 통해 연결된 데이터 집합체
    • 값뿐만 아니라 참조를 저장하는 데이터 공간이 필요함.
    • 각 원소는 자신의 값과 다음에 연결된 참조 값을 가진다.
  • O(n)으로 접근 및 검색, O(1)로 삽입 및 삭제 가능
    • 하지만 원하는 위치에 삽입, 삭제를 하기위해서는 여전이 O(n) 시간이 걸린다.
  • 연결 리스트는 트리(Tree)자료구조를 구현할 때 사용된다