배열 Array
일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조
선언 시 크기를 반드시 지정해야 한다.
각 요소에는 0부터 시작하는 고유한 순서 번호인
인덱스(index)가 매겨진다.
시간복잡도
인덱스를 바탕으로 배열의 특정 요소에 접근하는 시간 :
O(1)인덱스를 바탕으로 특정 요소를 수정하는 시간 :
O(1)N개의 데이터에서 앞부터 차례대로 특정 요소가 있는지를 찾는 연산 시간 :
O(N)특정 요소를 추가하거나 삭제하는 연산 시간 :
O(N)중간에 추가 또는 삭제된 요소르 인해 이후의 요소들이 이동 및 재정렬되기 때문
연결리스트 Linked List
노드의 모음으로 구성된 자료구조
노드 = 저장하고자 하는 데이터 + 다음 노드의 위치 (메모리 상의 주소)
모든 노드들이 한 쪽 방향으로 꼬리에 꼬리를 무는 형태로 구성
연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 유용
시간복잡도
특정 요소에 접근할 때는 앞에서부터 순차적으로 접근 :
O(n)새로운 노드를 삽입 또는 삭제할 때 연산 시간 :
O(1)
종류
1. 싱글 연결 리스트 (Singly linked list)
탐색은 단방향으로만 가능하다.
특정 노드를 통해 다음 노드의 위치만 알 수 있고, 이전 노드의 위치는 알기 어렵다.
2. 이중 연결 리스트 (Doubly linked list)
노드 내에 다음 노드의 위치 정보뿐만 아니라 이전 노드의 위치 정보도 포함하고 있다.
싱글 연결 리스트와 달리 양방향 탐색도 가능하다.
한 노드에 2개의 위치 정보(메모리 주소)를 저장해야 하므로 그만큼의 저장 공간이 더 필요하다.
3. 환형 연결 리스트 (Circula linked list)
꼬리 노드가 헤드 노드를 가리켜 노드들이 원형으로 구성된 연결 리스트
모든 노드 데이터를 여러 차례 순회해야 할 때 유용하게 활용할 수 있다.