Data structure - part.1

자료구조란?

 

데이터의 표현 및 저장 방법.

자료를 어떻게 효울적으로 조직 , 관리 , 저장 할 것 인지에 대한 방법.

 

자료구조의 구성
1. insert :  저장

2. Search : 탐색

3. Delete : 삭제

 

일반적으로 자료구조는 단순구조, 파일구조, 선형, 비선형구조로 나뉘며,

 

선형구조(Linear)와 비선형구조(Non-Linear)를 말한다.

 

1. Stack

stack 은 기본적으로 LIFO ( Last In First Out ) 를 모토로 해서 가장 마지막에 들어온 데이터가 가장 먼저 나가는 형식이다.

 

1-1 Stack 의 구조 

 

stack 의 구조는 크게 3가지로 나누어진다. 

 

데이터가 들어오는 과정인 Push

데이터가 나가는 과정인 Pop
최근 데이터를 확인하는 Peek

파란 상자가 마지막으로 들어오는 과정 push , 최근 데이터가 누군지 확인하는 peek , 파란상자가 다시 마지막으로 나가는 pop 을 
그림으로 설명해보았다.

 

1-2 Stack 구현

 

Array 에 Array.push() 로 맨 뒤에 새 엘리먼트를 추가하고 Array.Pop() 으로 맨 뒤 엘리먼트를 제거하는 방식.

 

 

1-3 의사코드

데이터 쌓일 공간 Array 인 stackArr 생성

stackArr 에 data 가 push 되는 경우 
push 함수 생성 , 인자로 data 를 받음

stackArr.push(data) 배열 맨 뒤에 데이터 추가

stackArr 에 data 가 pop 되는 경우 
pop 함수 생성 

stackArr 에 pop() 배열 맨 뒤의 데이터 삭제

공통
peek 변수를 생성 = stackArr[stackArr.length-1] peek 값을 리턴하고
count 변수를 생성 = stackArr.length  데이터의 갯수 파악
[stackArr,peek,count] 리턴

---

2. Queue

Queue 은 기본적으로 FIFO ( First In First Out ) 를 모토로 해서 가장 먼저 들어온 데이터가 가장 먼저 나가는 형식이다.

 

2-1 Queue 의 구조 

 

Queue 의 구조는 크게 2가지로 나누어진다. 

 

데이터가 들어오는 과정인 enqueue

데이터가 나가는 과정인 dequeue

파란 상자가 마지막으로 들어오는 과정 enqueue , 가장 먼저 들어와있던 파란상자가 가장 먼저 나가는 dequeue 를 
그림으로 설명해보았다.

 

2-2 Queue 구현

 

Queue 의 구조도 Array 에 Array.push() 로 맨 뒤에 새 엘리먼트를 추가하고 Array.shift() 으로 맨 앞 엘리먼트를 제거하는 방식.

 

 

2-3 의사코드

 

데이터 쌓일 공간 Array 인 queueArr 생성

queueArr 에 data 가 enqueue 되는 경우 
enqueue 함수 생성 , 인자로 data 를 받음

queueArr.push(data) 배열 맨 뒤에 데이터 추가

queueArr 에 data 가 dequeue 되는 경우 
dequeue 함수 생성 

queueArr 에 shift() 배열 맨 앞의 데이터 삭제

공통
peek 변수를 생성 = queueArr[queueArr.length-1] peek 값을 리턴하고
count 변수를 생성 = queueArr.length  데이터의 갯수 파악
[queueArr,peek,count] 리턴

---

 

Linked List

데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하고 있는 구조.

 

장점 : 노드의 중간지점에서도 자료의 추가와 삭제가 짧은 시간에 가능하다.
단점 : 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는시간이 걸린다.

연결리스트는 요소를 배열처럼 차례대로 저장하지만 요소들이 메모리상에서 연속적으로 위치하지 않는다.

 

1. 요소들끼리 다음 요소를 가리키는 포인터를 가지고 있고 다음 요소로 연결된다.

2. 마지막 항목은 Null 을 가리킨다.

3. 크기 조절이 용이하다. ( 추가,삽입,삭제가 용이 )

4. 메모리가 허용하는 한 필요만큼 길어질 수 있다.

5. 메모리 공간 낭비가 적다.

6. 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 일반적으로 탐색 속도가 떨어진다.

* 데이터를 저장할 장소'와 '다른 변수를 가리키기 위한 장소'가 구분되어 있다.

 

배열리스트와의 차이점. pointer 부분을 head로 칭했다.

 

 

의사코드

+맨 앞을 head , 맨 뒤를 tail 로 칭한다.

새 노드 생성.
Node[Data,head] 생성
LinkedList 만들기

새 노드를 추가하는 경우

새로 추가되는 값이 null 인지 확인.

빈 리스트일 때
this.head 가 null 일 것이므로 head 가 새 노드를 가리키게 한다.

비어있지 않는 리스트일 때
현재 위치의 다음 노드가 null 이 될 때까지 리스트를 탐색
while(current.next){ current = current.next}

노드 삭제

첫 번째 노드를 삭제할 때
조건 position 이 0일 때
head 를 두번 째 노드로 교체. head = curr.next

원하는 위치의 노드를 삭제할 때
삭제되는 노드의 앞 노드의 헤더를 삭제되는 노드의 주소값으로 교체

 

연결리스트의 종류

 

1. 단일 연결 리스트

각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

 

 

2. 이중 연결 리스트

단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

 

 

3. 원형 연결 리스트

일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.