배열
일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조
각 요소에는 0부터 시작하는 고유한 순서 번호인 index가 매겨지고 index로 배열의 요소를 식별
인덱스를 통해 특정 요소에 접근, 수정하는 시간 O(1)
앞부터 차례대로 특정 요소가 있는지를 찾는 시간 O(n) : 데이터를 찾을 때까지 탐색하기 때문
특정 요소를 추가하거나 삭제하는 시간 O(n) : 중간에 추가/삭제된 요소로 인해 이후의 요소들이 이동해야 하기 때문
이차원, 삼차원 배열로 확장할 수 있음
이차원 배열은 배열 속에 배열이 포함된 경우로, 2개의 인덱스로 요소를 식별
삼차원 배열은 배열 속에 배열 속에 배열이 포함된 경우, 3개의 인덱스로 요소를 식별
정적 배열 : 프로그램을 실행하기 전에 크기가 고정되어 있는 배열, 실행 도중에 크기를 변경하지 못함
C++의 std::array
동적 배열 : 실행 과정에서 크기가 변할 수 있는 배열
프로그램을 실행하기 전에 배열의 크기를 알기 어려운 경우, 요소의 개수를 변경해야 하는 경우 사용
C++의 std::vector
연결 리스트(linked list)
노드의 모음으로 구성된 자료구조
노드 : 데이터와 다음 노드의 위치(메모리 상의 주소) 정보를 포함하는 연결 리스트의 구성 단위
헤드 : 연결 리스트의 첫 번째 노드
꼬리 : 연결 리스트의 마지막 노드
연결 리스트를 구성하는 모든 노드는 반드시 메모리 내에 순차적으로 저장되어 있을 필요가 없기 때문에 연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 사용
싱글 연결 리스트
특정 요소에 접근할 때는 앞에서부터 순차적으로 접근해야 하므로 O(n)
노드에 바로 접근할 수 있다면 노드 삽입/삭제 O(1) : 배열에 비해 추가/삭제 연산에서 재정렬이 불필요
이전 노드의 위치를 알기 어려워 단방향 탐색만 가능
이중 연결 리스트(doubly linked list)
이전 노드의 위치 정보도 포함하고 있는 연결 리스트
양방향 탐색이 가능해 탐색 성능을 향상시킬 수 있지만 추가로 이전 노드의 메모리 주소를 저장해야 하므로 추가적인 저장 공간 필요
환형 연결 리스트(circular linked list)
꼬리 노드가 헤드 노드를 가리켜 노드들이 원형으로 구성된 연결 리스트
이중 연결 리스트로도 구현 가능