1. 자료구조란?
자료(데이터)의 효율적인 처리를 위해 자료들 간의 논리적 관계를 추상화를 통해 구조화한 것을 자료 구조라 부른다.
여기서 말하는 추상화란 시내버스, 고속버스, 공항버스 등을 묶어 버스라 부르고 버스, 지하철, 택시를 묶어 대중교통이라고 부르는 것처럼 자료들이 가지는 공통의 특징만을 뽑아 정의한 것이다.
개발자가 사용하는 프로그래밍 언어에서의 자료구조의 형태는 '미리 정의된 자료구조'와 개발자가 정의하여 사용하는 '사용자 정의 자료구조'로 구분된다. 미리 정의된 자료구조는 해당 언어가 설계단계나 컴파일러 단계에서 개발자에게 제공하는 자료구조이며 사용자 정의 자료구조는 개발 중 개발자에 의해 만들어진 리스트, 스택, 큐, 트리와 같은 자료구조이다.
부적절한 자료구조의 사용은 개발의 복잡도를 높이고 실제 사용 시에도 비효율적으로 수행되어 예상하지 못한 장애를 일으키기도 하며 차후 수정 개발 시 확장성과 장애처리 등 유지보수에도 악영향을 끼치게 된다.
2. 배열
같은 자료형의 여러가지 데이터들을 같은 이름의 변수 안에 저장하는 자료의 집합체로 볼 수 있다. 배열 안 데이터의 저장 순서는 프로그래밍 언어에 따라 차이는 있으나 순서대로 차례차례 메인 메모리에 저장하며 다차원 배열의 경우에는 행을 차례대로 저장하거나 열을 차례대로 저장하는 두 가지의 방법을 사용하고 있다. 저장된 배열 안의 각 항목의 접근은 0번부터 시작(언어에 따라 다를 수 있음)하는 인덱스로 꺼내어 사용할 수 있다.
3. 리스트
리스트는 1개 이상의 원소들이 순서를 가지고 구성되어 있는 것을 말한다.
일반적으로 리스트는 1차원 배열과 같이 순차적인 구조를 가지고 있어 리스트가 아닌 배열로 간단히 표시할 수도 있다.
하지만 일반적인 1차원 배열로 저장 후 데이터의 삽입이나 삭제가 일어날 경우에는 해당 위치 이후의 원소들이 한 칸씩 당겨지거나 밀리는 작업을 일일이 수행해줘야 한다. 따라서 빈번한 삽입 및 삭제가 있을 경우에는 포인터 변수를 활용한 연결 리스트(linked list)를 사용할 수 있다. 연결 리스트 안에서도 단일 연결 리스트와 이중 연결 리스트로 나눌 수 있다.
먼저 단일 리스트의 경우 각 노드는 value를 저장하는 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성되어 있다.
이렇게 구성함으로써 생기는 이점은 데이터의 삭제로 예를 들면 해당 주소의 뒷 데이터들을 모두 이동하는 것이 아닌 앞 노드의 주소 값을 삭제할 노드의 주소 값으로 변경하기만 하면 다른 데이터의 이동 없이 그대로 리스트를 유지할 수 있다. 단, 각 노드는 자신의 뒷 노드의 주소 값만을 가지고 있기에 후행 노드로의 접근은 용이하나 선행 노드로의 접근은 무조건 헤드로부터 시작해야 한다는 단점을 가지고 있다.
이를 보완하기 위해 나온것이 이중 연결 리스트로 단일 연결 리스트와는 다르게 선행 노드의 주소 값을 가지고 있어 양방향으로 비교적 효율적으로 탐색할 수 있다.
4. 스택
데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지는 자료구조로 쌓여있는 책 더미나 프링글스 통을 예로 들 수 있다.
스택에서의 삽입이나 삭제가 일어나는 부분을 top이라는 변수를 사용해서 가리킨다. 삽입시에는 top이 가리키는 바로 위쪽에 저장되고, 삭제 시에는 top이 가리키는 데이터를 삭제한다. 삭제와 삽입이 한쪽에서만 수행되기 때문에 후입 선출(LIFO, Last-In First-Out) 구조이다. 스택에서는 데이터의 삽입을 push, 삭제를 pop이라고 표현한다.
5. 큐
스택과는 다르게 양쪽에서 삽입 및 삭제가 이루어지는 자료구조로 줄을 선 순서대로 처리하는 은행 창구를 예로 들 수 있다. 큐에서는 먼저 들어온 데이터를 순차적으로 처리하기 때문에 선입선출(FIFO, First-In First-Out) 구조이다. 스택에서는 한쪽에서 삽입과 삭제를 모두 담당하기 때문에 top이라는 변수 하나만 사용하고 있으나 큐에서는 각 방향마다의 역할이 다르기에 가장 먼저 들어온 데이터를 처리하는 부분을 front, 가장 최근에 들어온 데이터를 처리하는 부분을 rear라고 부른다.