자료 구조는 크게 두가지로 분류된다. 선형구조와 비선형구조이다.
자료 구조의 의의는 적절한 자료구조의 선택은 결국 실행 성능의 향상을 가져온다.
어떠한 자료구조를 선택하는냐에 따라 프로그램이 달라지기 때문에 우리는 자료구조마다의 장단점을 정확히 파악해야한다.
선형구조에는 대표적으로 배열, 리스트(단일, 이중, 원형), 스택, 큐, 데크가 존재하고 비선형구조에는 대표적으로 트리와 그래프가 있다.
순차적으로, 배열부터 정리를 시작하겠다.
배열은 연속적인 메모리가 할당되는 공간이다. 각각의 메모리는 첨자를 통해 접근이 가능하다. 이때 첨자는 우리가 흔히 말하는 index를 뜻한다. 첨자는 무조건 0에서 1까지 순차적으로 증가되는 값을 가진다.
index의 특징으로 인해 Random access가 가능하다. Random access란 임의적인 접근이 가능한 상태다.
이는 배열의 가장 큰 장점이다.
반대로, 배열의 가장 큰 단점의 예시를 들겠다. 예를 들어 a[2]의 데이터를 삭제한다고 가정해보자.
a[2]의 2번 데이터를 꺼내기 위해서 먼저, a[3], a[4],a[5]등 뒤에 따라오는 메모리 값이 앞으로 당겨져야지만 a[2]의 데이터를 삭제할 수 있다. 즉, 배열 안의 메모리 하나를 삭제하기 위해서는 다른 메모리 값을 위치 조정해야한다는 것이다.
원소 하나를 삭제하기 위해 데이터의 이동이 너무 많이 움직이는 현상인 Overhead가 발생하게 된다. Overhead란, 프로그램을 실행하면서 발생되는 메모리나 실행 속도를 말하게 된다. 이때, Overhead가 높아졌다는 것은 메모리를 과사용했다는 것이다. 이러한 단점을 해결하기 위해서 나온 자료구조가 바로 리스트이다.
두번째로는 리스트이다.
배열에서 원소 a[i]라고 표현을 했다고 하면, 리스트에서는 원소 하나하나를 노드라고 일컫는다.
이 노드들은 덩어리채로 묶여져 있는 배열과는 상반되게 연결되어 있지 않다. 따라서 리스트에서는 배열과 다르게 어떤 노드가 1번째 노드인지 확인할 수 있는 방법이 없다. 그렇기 때문에 노드에서 헤드(head)가 필요하게 된다.
헤드가 의미하는 것은 첫번째 주소를 의미한다. 각 노드에 순서가 존재하지 않기 때문에 각각의 노드는 다음 노드를 가리킬 수 있는 포인터(변수)가 필요하게 된다.
연결 리스트의 단점
각각의 노드마다 다음 노드를 가리킬 포인터 변수가 필요하다. 이러하기 때문에 각 노드마다 8Byte의 데이터 저장 공간이 필요하게 된다. 예를 들어, 3번째 데이터 값을 호출하게 된다면, 연결 리스트의 1 번째 노드, 2 번째 노드 그리고 마지막 3 번째 노드를 걸쳐 a[2]번째 데이터를 찾아가서 와야하기 때문에, Random access를 접근하게 될때 무조건적으로 head부터 찾아가야한다. 그래서 프로그램 내에 데이터에 접근할 내용이 많아지게 된다면 배열과 리스트 중 배열이 훨씬 더 좋아진다.
연결 리스트의 장점
반대로, 노드 별 다음 포인터를 지정하기 때문에, 데이터 내 삭제가 이루어질때 해당하는 원소만 제거하게 되는 중간 삭제, 삽입이 빠르다. 데이터를 배열처럼 이동하지 않아도 되는 Overhead가 발생할 확률이 적다.
이중 연결리스트
+ 이중 연결 리스트는 양방향성 리스트이다. 앞 뒤 연결이 모두 가능한 리스티이다.
원형 리스트
앞에 있는 리스트와 뒤에 있는 리스트가 연결되어 Null이 존재하지 않는다.
스택이나 큐
한쪽으로만 삭제나 삽입이 가능한 자료구조이다.
삽입하는 작업을 Push, 삭제하는 작업은 Pop이라고 일컫는다. LIFO(Last In First Out)의 구조를 띈다.
큐는 한쪽방향으로 삽입이 이루어지고 반대쪽으로는 삭제가 이루어지는 한 줄 서기와 비슷하다.
삽입하는 작업을 enqueue, 삭제하는 작업을 dequeue라고 부른다.
삽입은 뒤에서 rear가 삭제는 앞에서 front가 이루어진다. 결국은 FIFO(First In First Out)의 구조로 이루어지게 된다.
가장 이해하기 편한것은 프린터를 예시로 할 수 있다.
큐를 구현한다고 했을때, 연결리스트가 더욱 효율적이다.
데크는 양쪽 방향에서 삽입과 삭제가 이루어진다.
두 번째로는, 순서를 갖지 않는 비선형 구조를 가진 트리나 그래프에 대해 알아보는 시간을 가지도록 하겠다.
트리는 부모와 자식 관계를 가진 자료구조이다. 우리는 이것을 트리라고 부른다.
그래프는 모든 노드들이 독립적으로 존재하며 시작이 없다.
