[자료구조의 형태]

자료구조란 ?

컴퓨터에서 사용할 자료를 더 효율 적으로 관리하기 위해서 자료의 특성과 사용 용도에 따라 분류하고 구조화 한것이다.

 

1. 단순 자료 구조

컴퓨터 프로그래밍에서 쓰이는 데이터 타입을 말한다.

ex) Int, double, string 등등등

 

 

2. 선형 구조

자료들 간의 관계가 1:1인 관계이다. 중요하니 자세히 살펴보자,

 

스택

후입 선출 LIFO(Last In First Out)  구조의 자료 구조 이다.  가장 최근에 추가한 항목이 가장 먼저 제거된다.

스택의 구조 [출처: 위키 백과]

삽입(push) 삭제(pop)의 경우 O(1)의 시간 복잡도가 걸린다.

모든 원소를 탐색하려면 일일히 옮겨 가면서 해야하고 맨 위에 원소만 접근 가능하다.
따라서, 보통 역 작업시에 사용한다. (ex.작업 취소)

 

큐

선입 선출 LIFO(First In First Out)  구조의 자료 구조 이다.  가장 먼저에 추가한 항목이 가장 먼저 제거된다. 스택과 반대되는 개념이다.

 

 

큐의 구조[출처:위키 백과]

삽입(push) 삭제(pop)의 경우 O(1)의 시간 복잡도가 걸린다.
모든 원소를 탐색하려면 일일히 옮겨 가면서 해야한다. 맨 앞의 원소만 가능하다.
데이터 갯수가 가변적이고 탐색이 불 필요할때 주로 사용한다.

 

디큐

Double-ended-queue의 약자로 양쪽 끝에서 삽입과 삭제가 모두 가능 한 자료 구조이다. 큐와 스택을 합친 자료 구조

삽입(push) 삭제(pop)의 경우 O(1)의 시간 복잡도가 걸린다.
보통 스케줄링,연결리스트 구현 시에 사용한다.

 

순차리스트

논리적인 순서와 물리적인 순서가 같은 구조. 메모리에 연속적으로 저장된다.무작위 접근이 가능하다.

배열(Array)의 구조

삽입,삭제,탐색의 경우 O(N)의 시간 복잡도가 걸린다. 물리적인 위치를 유지 하기 위해 옮기는 작업이 필요하다.

연결리스트

메모리에 저장된 물리적 위치나 순서와 상관 없이 링크에 의해 논리 구조가 형성 된다.노드가 데이터와 포인터를 갖고 한 줄로 연결 된 자료 구조이다.

연결리스트(Linked List) 의 구조

특정 노드의 삽입 삭제 시에, 노드의 링크 필드(다음 주소만) 수정 하면 되어서 연산 속도가 빠르다.무작위 접근이 가능하다.

 

 

 

2. 비선형 구조

 

그래프

노드(Node)과 노드를 연결하는 간선(Edge)로 이루어 진 자료 구조이다. 즉, 연결 되어 있는 객체간의 관계를 표현한 자료 구조이다.

 

그래프의 구조[위키백과]

 

트리

그래프의 일종으로 여러노드가 한 노드를 가르킬 수 없는 계층적 구조의 형태이다.사이클(cycle)이 없다.

트리의구조[출처:위키 백과]

그래프와 트리의 차이[출처 :그림 클릭]

[자료 구조별 시간 복잡도]