배열과 링크드리스트
다른 자료구조를 구현하는 기본이 되는 자료구조이다.
배열
가장 기본이 되는 자료구조이다. 논리적 저장 순서와 물리적 저장 준서가 일치하여 index로 해당 원소에 접근할 수 있다. 그래서 원하는 찾고자 하는 원소의 index를 알고 있으면 원소에 접근하는데 O(1)의 시간복잡도로 접근할 수 있다. 즉, random access가 가능하다.
배열에서 원소의 삭제와 삽입은 O(n)의 시간복잡도를 가진다. 삭제의 경우 해당원소에 접근하는 시간 복잡도는 O(1)이지만 삭제 이후 삭제된 원소는 빈공간으로 남아 있기 때문에 삭제한 원소보다 큰 인덱스를 갖는 원소들을 왼쪽으로 shift해주어야한아. 최악의 경우 가장 앞 원소를 삭제하였을 경우 n-1개의 원소를 모두 shift left 해야하기 때문에 삭제의 시간 복잡도는 O(n-1) = O(n)이다.
삽입의 경우에도 최악의 경우 가장 앞에 원소를 추가한다고 하였을 때, 모든 원소들을 shift right해야하기 때문에 시간복잡도 O(n)을 가진다.
링크드 리스트
링크드 리스트는 각 노드가 다음 노드를 가리키는 포인터를 가지고 있는 형태로, 현재 노드에 대한 정보가 있으면 다음 원소에 접근할 수 있다. 배열이 삽입과 삭제에서 시간 복잡도 O(n)을 갖는 데 반해 링크드 리스트는 해당 노드를 링크드 리스트에서 빼거나 삭제한 이후에 shift를 해줄 필요가 없기 때문에 삭제와 삽입에 대해서 O(1)을 갖는다. 하지만 삭제, 삽입하려는 위치에 접근하기 위해서는 첫번째 노드부터 하나씩 확인을 해야하기 때문에 search 단계에서 O(n)의 시간 복잡도를 갖기 때문에 결국 삭제와 삽입에서도 O(n)의 시간 복잡도를 갖는다.
비교
- 탐색의 경우 배열이 O(1), 링크드리스트가 O(n)이다.
- 삽입, 삭제의 경우 배열과 링크드리스트 모두 O(n)이지만 링크드 리스트의 경우 삽입과 삭제에 대한 절차가 더 간단하고, 배열은 삽입시 공간이 모두 찼다면, 새로 배열을 선언하여 데이터를 옮기는 과정이 필요하다.
따라서 데이터의 탐색이 주로 발생하는 경우 배열, 데이터의 삭제 및 삽입이 주로 발생하는 경우 링크드 리스트를 사용하는 것이 좋다.
Stack
선형 자료구조의 일종으로 LIFO(Last In First Out), 즉 후입선출의 형태를 가지고 있다. 새로 들어온 원소가 기존의 원소 위에 쌓이는 모양이기 때문에, 가장 최근에 들어온 원소가 가장 먼저 나가게 된다. 대표적인 예로 시스템 호출 스택이 있다.
스택의 대표적인 연산으로는 Push(const T& item), Pop(), Push(), Top(), IsEmpty()가 있다. Push(const T& item)를 통해 스택에 원소를 넣고, Pop()을 통해 스택에서 원소를 꺼낸다. Top()은 가장 위에 있는 원소의 정보를 확인하는 연산이다. IsEmpty()는 스택이 비었는지 확인하는 연산이다. Pop(), 이나 Top()을 수행하기 전에 꺼낼 원소가 있는지 확인할 때 사용한다.
Queue
선형 자료구조의 일종으로 FIFO(First In First Out), 선입선출의 형태를 띄고 있다. 먼저 들어간 원소가 가장 먼저 나오는 형태이다.
큐의 대표적인 연산에는 Front(), Rear(), Push(const T& item), Pop(), IsEmpty()가 있다. Front()는 큐에 들어온지 가장 오래되어 다음 Pop() 수행 시 큐에서 꺼내지는 원소(큐의 가장 앞)를 확인하는 연산이고, Rear()는 큐에 가장 최근에 들어온 원소(큐의 가장 뒤)를 확인하는 연산이다. Push(const T& item)는 Rear()가 가리키는 다음 위치에 item을 넣는 연산이다. Pop()은 Front()가 가리키는 원소를 큐에서 꺼내는 연산이다. IsEmpty()는 큐가 비었는지 를 확인하는 연산이다. Pop()연산이나 값을 조회할 때 IsEmpty()를 사용하여 큐에 원소가 있는지 확인한다.
참조 (https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure)
