본 글은 깃허브에 올라온 자료 구조 정리(https://github.com/Seogeurim/CS-study/blob/main/contents/data-structure/basic.md#array-%EB%B0%B0%EC%97%B4) 글을 보고 정리한 글입니다.
자료 구조(Data Structure)란? 자료에 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법을 의미한다.
선형 자료 구조: 데이터가 일렬로 나열되어 있음.(array, linked list, stack, queue)
비선형 자료 구조: 데이터가 특정한 형태로 있는 것(tree, graph)
Array(배열)
동일한 자료형의 데이터를 일렬로 나열한 자료구조
1. 선형 구조
2. 데이터 접근이 용이하다. (인덱스로 접근, Random access가 가능)
3. 데이터 삽입/삭제가 어려움(Shift 해줘야 함)
4. 구조가 간단하여 프로그램 작성이 쉬움
Array 시간 복잡도
데이터 조회: O(1)
데이터 삽입/삭제: O(n)
Linked List(연결 리스트)
각 노드가 데이터와 포인터를 가지고 일렬로 연결되어 있는 방식
1. 선형 자료 구조
2. 데이터 접근이 느림(링크를 타고 가서 찾아야 한다.)
3. 데이터 삽입/삭제 연산이 용이함.
4. 포인터를 위한 추가 공간 필요
Singly Linked List, Doubly Linked List
Linked List 시간 복잡도
데이터 조회: O(n)
맨/앞 데이터 삽입/삭제: O(1), but Singly Linked List는 데이터 삭제 연산 O(1)
중간에 원하는 위치에 데이터 삽입/삭제: O(n) 원하는 원소까지 이동이 O(n), 삭제가 O(1)이므로 O(n)+O(1)
Array와 Linked List 차이
1. 데이터 접근 속도: Array는 인덱스를 통한 랜덤 엑세스가 가능하여 데이터를 O(1)으로 빠르게 찾을 수 있음. Linked List는 순차 접근 방식을 사용하므로 O(N)이 걸린다.
2. 데이터 삽입/삭제 속도: Array는 데이터를 중간이나 맨 앞에 삽입/삭제하는 경우 shift가 필요하므로, 데이터가 많을수록 비효율적.
Linked List는 중간/삽입 삭제는 똑같이 O(N)이 걸리지만, 맨 앞 또는 뒤에 삽입할 경우 O(1)의 시간 복잡도를 갖는다.
3. Linked List는 데이터 삽입/삭제마다 메모리 할당/해제가 일어나므로, 시간 복잡도는 빠를지라도, 시스템 콜이 Array보다 더 시간이 걸린다.
메모리 할당
1. Array는 정적 메모리 할당(Compile time)이 일어난다.
2. Linked List는 동적 메모리 할당(Runtime)이 일어난다.
3. Array는 데이터 삽입 시 모든 공간이 다 차버리면 새로운 메모리 공간이 필요하지만, Linked List는 동적으로 할당 가능하다.
[정리]
데이터 삽입/삭제가 빈번하다면, Linked List를 사용하는 것이 좋고, 데이터 접근 속도가 중요하다면 Array를 쓰자.