[자료구조] 리스트, 스택, 큐, 트리, 그래프

자료구조란?

자료구조는 자료에 대한 처리를 효율적으로 수행할 수 있도록 구분지어 놓은 것을 말한다. 

 

짐을 정리해서 공간을 확보하는 것처럼'자료구조'를 이용해 데이터를 잘 정리해 놓으면 데이터를 보다 효율적으로 저장하고 관리할 수 있다. 코드의 처리 시간을 단축시키고 메모리의 용량도 줄여주는 효과를 가져오는 것이다. 

 

자료구조의 종류

자료구조는 크게 선형구조와 비선형구조로 나눌 수 있다.

선형구조

1. 선형 리스트(Linear List)

배열(Array)가 여기에 해당한다.  배열은 입력된 데이터가 메모리 공간에서 연속적으로 저장되어 있는 구조이다.  

연속적으로 저장되어 있는 특징 때문에 index를 통한 접근이 용이하나 배열의 처음 또는 중간에 데이터의 삽입, 삭제는 번거롭다.

2. 연결 리스트(Linked List)

연결 리스트는 배열과 다르게 연속된 메모리 공간에 저장되어 있지 않다. 데이터를 저장하는 공간과 그 다음에 나올 데이터가 저장된 공간을 가르키는 주소값을 동시에 가지고 있다. 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재하며, 이 노드는 자신의 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 기억하고 있다.

 

접근이 head부터 순차적으로 이루어져 배열보다 느린편이나 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.

배열은 빠른 접근이 요구되고 데이터의 삽입과 삭제가 적을 때 사용하는것이 유리하고,
연결리스트는 삽입과 삭제가 잦고 검색 빈도가 적을 때 사용하는것이 유리하다.

3. 스택 (Stack)

스택은 차곡차곡 쌓아 올린 형태의 자료구조로 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조이다.

정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.

(LIFO, Last In First Out 마지막이 처음에 나온다.)

스택 활용 예시

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.

4. 큐(Queue)

큐는 줄을 서서 기다리는 것과 비슷하다. 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조이다.

큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 이루진다.

(FIFO, First In Last Out 마지막이 처음에 나온다.)

 

큐 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 쇼핑몰 주문 처리 시스템
• 프로세스 관리

비선형구조

개체 간의 관계를 나타내는 데 사용되는 데이터 구조이다. 

 

1.  트리(Tree)

트리는 각 노드가 최대 하나의 부모를 가질 수 있고 구조에 순환(즉, 루프)이 없는 그래프 유형이다.

트리는 일반적으로 컴퓨터의 파일 시스템이나 회사 조직과 같은 계층적 관계를 나타내는 데 사용된다.

항상 구조의 최상위 노드인 루트라는 단일 노드가 있다.

 

2. 그래프

그래프는 부모와 주기를 얼마든지 가질 수 있는 보다 유연한 구조이다.

그래프는 반드시 계층적이지 않은 개체 간의 관계를 나타내는 데 사용된다.

지정된 루트 노드가 없으며 각 노드는 여러 개의 이웃을 가질 수 있다.

 

 

두 가지 구조를 요약하면 트리는 계층적 구조를 갖고 있고 순환이 없는 유형의 그래프인 반면,

그래프는 모든 유형의 관계와 순환을 가질 수 있는 보다 유연적인 구조 입니다.