[c++] 순차 자료 구조와 연결 자료 구조

자료 구조는 크게 순차 자료 구조와 연결 자료 구조로 구분할 수 있다. 

 

순차(Sequntial) 자료 구조

순차 자료 구조는 모든 데이터를 단일 메모리 청크에 연속하여 저장한다. 데이터가 메모리에 저장될 때, 저장 시작 위치부터 빈자리 없이 순서대로 저장된다.

이 그림을 보면 각각의 데이터는 int형으로 모두 같은 타입이다. 첫번째 원소의 메모리 주소를 시작 주소(Base Address)라고 하는데 그림에서의 시작 주소는 100이다. 주어진 모든 데이터의 타입이 같기 때문에 두번째 데이터는 시작 주소(100)+sizeof(int)로 104이다. 세번째 데이터는 시작 주소(100)+2*sizeof(int)로 108이다.

cf) int 타입은 4byte

자료 구조에서는 배열의 전체 크기에 관계없이 모든 데이터에 바로 접근할 수 있다. 만일 i번째 데이터에 접근하고 싶다면, 시작주소(Base Address)+i*sizeof(type) 수식을 사용한다. 따라서 데이터 접근 시간은 항상 동일하다. 시간 복잡도(Time complexity)의 빅오(Big-O) 표기법으로 나타내보면 O(1)이다.

 

배열의 유형은 크게 정적(static) 배열과 동적(dynamic) 배열이 있다.

	정적 배열	동적 배열
기능	선언된 블록이 끝나면 소멸	사용자가 생성할 시점과 해체할 시점을 결정 가능
성능	다양한 연산에서 동일한 성능을 보여줌
선언	int arr[size];	int *arr = (int *)malloc(size*sizeof(int)); or int *arr = new int[size];
할당	스택(stack)	힙(heap)
메모리 해제	함수를 벗어날 때 자동으로 해제	사용자가 직접 해체하기 전까지 유지

 

 

 

연결(Linked) 자료 구조

연결 자료 구조는 노드라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 메모리에 저장된 물리적 위치나 순서와 상관없이, 링크에 의해 논리적인 순서를 표현하는 자료구조입니다.

앞서 봤던 배열처럼 연속적인 메모리에 저장되는 방식이 아닌 노드라는 각각의 독립된 공간을 사용해 데이터를 담는다. 노드는 실제 데이터가 저장되는 공간인 데이터 필드와 다음 노드의 주소 값을 가진 링크 필드로 이루어져 있다.

위와 같은 형태로 구성된 자료 구조를 연결 리스트라고 한다. 연결 리스트의 기본 구조에서 각각의 노드는 저장할 데이터와 다음 노드를 가리키는 포인터를 가지고 있다. 맨 마지막 노드에서는 다음 노드의 포인터 대신 자료 구조의 끝을 나타내는 NULL을 가진다. 연결 리스트에서 특정 데이터에 접근하려면 리스트의 시작 부분, 즉 헤드 부분부터 시작하여 원하는 데이터데 도달할 때까지 next 포인터(링크 필드)를 따라 이동해야 한다. 그러므로 i번째 데이터에 접근하려면 연결 리스트 내부를 i번 이동하는 과정이 필요하다. 따라서 데이터 접근 시간은 노드 개수(n)에 비례하며, 시간 복잡도의 빅오(Big-O) 표기법으로 나타내보면 O(n)이다.

배열과 달리 연결 리스트는 포인터를 이용해서 데이터의 삽입 또는 삭제를 매우 빠르게 처리할 수 있다. 

위와 같이 새로운 노드(new_node, 2)를 삽입하려면 일단 새로운 노드를 생성하고, 삽입될 위치의 앞 노드(1)의 next포인터를 수정해야 한다. 삽입될 위치의 앞 노드(1)의 next 포인터를 새로운 노드(2)를 가리키게 변경하고 새로운 노드(2)의 next 포인터는 기존의 1번 노드가 가리키던 3번 노드를 가리키도록 해야 한다. 이러한 방식으로 새로운 노드가 연결리스트에 추가된다.

 

기존 데이터를 제거하려면 삭제할 데이터가 더이상 연결 리스트에 연결되어 있지 않도록 next 포인터를 수정해주면 된다. next 포인터를 수정해준 뒤, 삭제할 노드의 메모리 할당을 해제하거나 혹은 다른 처리를 통해 제거할 수 있다.

 

 

비교

순차 자료 구조	연결 자료 구조
모든 데이터가 메모리에 연속적으로 저장	데이터는 노드에 저장되고, 노드는 메모리 곳곳에 흩어져 있을 수 있음
임의 데이터에 즉각적으로 접근 가능	임의 데이터에 접근하는 것은 O(n) 복잡도를 가지며 느림
데이터가 연속적으로 저장되어 있고, 캐시 지역성 효과로 모든 데이터를 순회하는 것이 매우 빠름	캐시 지역성 효과가 없기에 모든 데이터를 순회하는 것이 느린편
데이터 저장을 위해 정확하게 데이터 크기만큼의 메모리를 사용	각 노드에서 포인터 저장을 위해 여분의 메모리를 사용

추가·삭제에서는 연결 리스트가, 탐색에서는 순차 리스트가 더 효율적인 자료구조라고 할 수 있다.

 

 

brightwon.tistory.com/3

[자료구조] 리스트(List) 이해하기

www.slideshare.net/LeeKeonHee2/ss-102565716

연결 리스트(기초)

www.yes24.com/Product/Goods/95863013

코딩 테스트를 위한 자료 구조와 알고리즘 with C++