자료구조 개념

우리가 무언가를 찾을때 정리되어 있으면 더 찾기 쉬워진다.
예를 들어서 옷을 정리할 때 상의, 하의, 양말 등 구별해서 정리하면 나중에 찾을 때 더욱 찾기 쉬워질 것이다. 즉, 예시와 같이 알기 쉽게 정리해서 메모리 공간을 효율적으로 관리하고 빠르게 찾기 위한 것을 자료구조 개념이라고 한다.

1. List

리스트는 배열과 유사한점을 볼 수 있다. 하지만 배열과 달리 크기를 자유자재로 조절할 수 있는것을 장점으로 보고있다. 배열보다 효율적인 데이터 및 자원 관리가 가능하기 때문에 리스트의 사용을 권장하고 있다.

class Program
		{
     	static void Main()
        	{ 
            	List<int> list = new List<int();         
					 list.Add(2);        
 					list.Add(3);        
 					list.Add(5);        
 					list.Add(7);    
			}
		}

2. Linked List

각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조를 Linked List라고 한다. 메모리의 효율적인 사용이 가능하며 동적으로 크기를 변경할 수 있다.
하지만 접근시간이 O(n)의 시간을 가질 수 있고, 포인터를 통해 다음 요소를 참조해서 캐시 효율성이 떨어질 수 있다.
링크드 리스트의 핵심 요소는 다음과 같다.
1) Node : 데이터를 저장하는 데이터 필드 와 다음 노드를 가리키는 링크 필드로 구성된다.
2) 포인터 : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
3) 헤드 : 링크드 리스트의 가장 첫 번째 위치
4) 테일 : 링크드 리스트에서 가장 마지막 위치

Linked List의 종류는 다음과 같다.

1) 단일 연결 리스트 : 노드를 가리키는 하나의 잠조만을 가지고 있는 기본 형태이다.
2 이중 연결 리스트 : 두개의 참조를 가지고 있으며, 하나는 다음 노드를, 다른 하나는 이전 노드를 가리킨다. 양방향으로 탐색할 수 있는 장점이 있다.
3) 원형 연결 리스트 : 첫 번째 노드가 마지막 노드와 연결되어 있는 시작으로 돌아오는 형태이다.

3. Stack

자주 접해봤을 단어이며 우리가 알고 있는 그 구조도 맞다.
순서가 보존되는 선형 데이터 구조를 갖는다.
스택은 x1, x2, x3, x4, x5 구조로 보존되면 x5부터 처리하는 LIFO(Last In First Out)구조를 갖는다. 이미 저장된 데이터를 건너뛰거나 데이터를 삽입할 수 없기에 처리 순서가 보장된다.

4. Queue

스택과는 반대로 가장 먼저 입력된 요소를 처리하는 FIFI(First In First Out) 구조를 갖는다. 스택과 달리 큐의 끝에서 데이터를 추가하거나 삭제할 수 있어 유연성이 높은 편이다. 하지만 추출하기 위해서는 앞의 데이터를 모두 추출해야하며, 데이터 삽입 위치가 고정되어 성능 향상이 어렵다.