0. 시작하기

 - 대표적인 알고리즘 몇개를 10개정도의 게시물로 나눠 살펴볼 예정입니다.

 - 초점이 알고리즘인 만큼, 다양한 포인터의 활용이나, 복잡한 문법의 사용이 적은 파이썬을 통해 풀어낼 예정입니다.

 - 복습 차원에서 진행하다보니 특정 자료형에서 많이 사용되는 알고리즘임에도 깜빡하고 넘어갈 수 있으며, 내용에 오류가 있을 수 있습니다. 이러한 부분이 있으실 경우 댓글 부탁드리곘습니다.

 - 시작은 간단한 자료형에 대한부분으로 시작하겠습니다.

 

1. 리스트(List)

배열과 비교되는 자료 형태로, 일반적으로 크기를 미리 정해두고 순차적으로 자료를 저장하여 관리하는 배열과 다르게, [데이터와 포인터]의 형태로 만들어져, 포인터를 통해 연결되어 크기를 미리 정하지 않고도 얼마든지 객체의 추가와 제거가 가능한 데이터 형태입니다.

 

단일 연결리스트(출처 : 위키)

배열과 다르게 무한히 새로운 데이터를 연결하여 만들어 줄 수 있다는 장점이 있지만, Index를 통해 특정 데이터를 한번에 호출 할 수 없다는 단점도 있습니다. 때문에, 최악의 경우 N개의 객체를 갖은 리스트에서 특정한 값을 찾기위해서는 N번 탐색을 해야할 수 있습니다.

 

또한 위와같은 단일연결리스트에서는 다음 객체에 대한 포인터만을 갖기 때문에 이미 지나간 값을 참조하기 위해서는 다시 처음부터 리스트를 탐색해야하는 문제가 있습니다. 때문에 아래와 같이 여러 목적을 위한 몇가지 형태가 생겼습니다.

 

이중 연결리스트(출처 : 위키)
단순 원형 연결리스트(출처 : 위키)

 

 2. 스택(Stack)

대표적인 LIFO(Last In First Out)의 자료형입니다. 입력되는 데이터가 층층이 쌓이는 형태로 주로 아래 그림과 같이 표현되며, 운영체제, 메모리에 대한 개념을 다룰때 많이 다루는 자료형입니다.

 

스택(출처 : 위키)

 

3. 큐(Queue)

대표적인 FIFO(First In First Out) 형태의 자료형입니다. 네트워크에서 라우터, 스위치와 같이 데이터(패킷)를 수신하여 특정한 방향으로 다시 발송하는 형태(순차적인 처리)에서 많이 채용되어 사용중에 있습니다.

 

 

4. 정리

대표적인 자료형이고, 대부분의 언어에서 기본으로 제공하거나 대표적인 라이브러리로 제공되는 자료형이기 때문에 코드로 구현해보지는 않았습니다.

특히 스택이나 큐의 경우 단순한 배열에 포인터만 추가하면 되는 형태이기 때문에 더욱이 별도로 코드를 첨부하지는 않았습니다.

궁금한 부분은 댓글로 남겨주세요~

+ Recent posts