경일 메타버스 20220620 12주차 1일 수업내용. 자료구조와 알고리즘

• 선형 리스트와 연결 리스트 모두 잘 알고 있어야 한다.

• 다른 자료구조의 베이스가 되기 때문.

자료

https://docs.google.com/document/d/1wUms27Vj8si-jEjfRQJwSvsQ2CJNCv4IU6GOtesY4TE/edit

연결 리스트

• 선형 리스트와 다르게 임의 접근이 불가능하다.

  • 선형 리스트가 주소 연산이 가능한 이유 :
    연속적으로 메모리가 할당되어 있기 때문 ⇒ 임의 접근이 가능.

  • 연결 리스트가 주소 연산이 불가능한 이유 :
    연속적이지 않기 때문 ⇒ 파편화 되어있다. 임의 접근 불가.

    • 다만, 반복자에 대한 증감연산자로 다음 메모리로 이동이 가능하다.

• STL 상에서의 구현

  • std::forward_list :
    https://en.cppreference.com/w/cpp/container/forward_list

  • std::list :
    https://en.cppreference.com/w/cpp/container/list

• 읽기
  연결 리스트는 임의 접근이 불가능해 요소 하나하나를 탐색해야 하므로 O(n)의 시간이 걸린다. 하지만 처음과 끝이라면 구현에 따라 O(1)이 될 수 있다.

• 검색
  하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다. 선형 리스트와 다르게 이진 검색을 사용할 수 없다.

• 삽입
  원소를 어디에 삽입하냐에 따라 시간이 달라진다. 앞이나 뒤에 데이터를 추가할 경우 O(1)이지만, 중간이라면 해당 위치까지 검색해야 하기 때문에 O(n)이 걸린다.
  ⇒ 위치를 안다 → O(1) / 위치를 모른다 → O(n)

• 삭제
  삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다. 앞이나 뒤의 데이터를 삭제할 경우 O(1)이지만, 중간이라면 O(n)이 걸린다.
  ⇒ 위치를 안다 → O(1) / 위치를 모른다 → O(n)

• std::forward_list
  std::forward_list는 다음 원소로만 이동할 수 있는 단일 연결 리스트이다.

  

• 단일 연결 리스트 :
  https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm

  2022. 06. 20 단일 연결 리스트 std::forward_list 사용 예시 코드

• std::list
  std::list는 이전 원소로도 이동할 수 있는 이중 연결 리스트이다.

  

• 이중 연결 리스트 :
  https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

  2022. 06. 20 이중 연결 리스트 std::list 사용 예시 코드

  • using byte = int; <⇒ typedef int byte;

  

• 노드 :
  교점, 각 연결된 객체.

• GoF의 디자인 패턴 :
  객체지향 설계의 필독서