TigerCow.Door

안녕하세요.

이번 포스팅에서는 파이썬을 이용하여 링크드 리스트를 구현해보도록 하겠습니다.



1. 링크드 리스트(Linked list)란?


먼저 링크드 리스트가 무엇인지 간단히 살펴보도록 하겠습니다.



링크드 리스트는 위와 같이 세개의 형태를 가지고 있습니다.

그림에서 두번째, 양방향 연결 리스트는 *Prev 가 자신보다 앞의 요소를 가르키는 것입니다.

단순히 단방향 연결리스트를 구현하면 어떤 요소의 앞의 요소를 탐색하기 위해서 결국 다시 처음부터 검색을 진행해야 하는 일이 발생할 수 있기 때문에 수행능력이 보다 안좋을 수 있습니다.

이러한 것을 보완하기 위해 양방향 연결 리스트 및 환형 연결 리스트라는 개념이 있는데, 이들은 단방향 연결 리스트보다 구현하기는 상대적으로 어려울 수 있지만 앞에서 말씀 드린 상황과 같을 때 보다 효율적으로 수행될 수 있습니다.



2. 단방향 연결 리스트 구현하기


이번 포스팅에서는 단방향 연결 리스트만 구현해보도록 하겠습니다.

기본적으로 Node 클래스와 LinkedList 클래스를 구현하였습니다. Node 클래스는 단순히 새로운 노드를 만들어 리스트에 삽입할때 사용됩니다.

LinkedList는 insert, delete, search, print, listNum 의 함수를 가집니다.

insert는 사용자가 지정한 값을 리스트의 맨 뒤에 삽입시키며 delete는 첫 번째 요소를 출력하며 이를 삭제합니다. search는 사용자가 지정한 값이 리스트의 몇번째에 있는지 탐색합니다. print는 현재 리스트를 출력해주고 listNum은 리스트의 요소가 몇개인지 출력합니다.


이를 구현한 전체 파이썬 코드는 아래와 같습니다.

LinkedList 자료구조 코드 보기


추가적으로 궁금한 사항이나 잘못된 점이 있으면 댓글을 남겨주세요 :)

블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

안녕하세요.

이번 포스팅에서는 파이썬으로 큐 자료구조 구현에 대한 내용을 소개해드리도록 하겠습니다.


1. 큐(Queue)란?


먼저 큐 자료구조에 대해서 간단하게나마 알아보도록 하겠습니다.



큐 자료구조는 위의 그림과 같이 요소(item)을 삽입하는 Enqueue 기능과 요소를 빼내는 Dequeue 기능이 있습니다.

그리고 처음에 삽입한 요소가 먼저 빠지게 되는 First In First Out(FIFO) 특징을 가지고 있습니다.



2. 큐(Queue) 구현하기


제가 파이썬 코드로 구현한 큐 자료구조는 위에서 말씀드린 Dequeue 기능과 Dequeue 기능을 포함한, 큐가 비어있는지 확인하는 isEmpty 기능을 구현하였으며 추가로 큐가 비어있을때 Dequeue를 수행하면 에러메세지와 함께 False 값을 리턴하게 하였습니다.


완성된 코드는 아래와 같습니다.


Queue 자료구조 코드 확인하기



추가적으로 궁금한 사항은 댓글을 이용해주세요.

블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

안녕하세요.

최근 파이썬을 공부하면서 기본적인 자료구조 알고리즘을 구현해보고자 생각이 들어서 포스팅을 하게 되었습니다.

제 노트북이 고장나서 노트북은 센터에 고이고이 잠들어있기 때문에.. 구름IDE로 코딩을 진행하였습니다.

나름 괜찮다고 생각이 드네요.


그럼 파이썬으로 구현한 스택 자료구조 소개해드리도록 하겠습니다.


1. 스택이란?


먼저 스택 자료구조를 구현하기 전에 간단하게나마 해당 자료구조에 대해 알아보도록 하겠습니다. 



위의 그림과 같이 스택은 push와 pop이라는 기능을 가지고 있습니다.

스택 자료구조는 말 그대로, 쌓아 올리는 것과 같은 자료구조입니다.

즉, push은 item을 쌓아올리는 기능이고, pop은 쌓여져 있는 item에서 제일 위의 것을 꺼내는 작업입니다.

따라서 스택 자료구조는 Last In First Out(LIFO) 와 같은 특성을 가지고 있습니다.



2. 스택 구현하기


제가 파이썬 코드로써 구현해볼 것은 클래스로 스택개체를 만들고, push와 pop기능을 구현하고 해당 스택이 비어있는지 확인하는 isEmpty기능까지 구현합니다.

또한 스택이 비어있을때 pop기능을 시도하면 에러메세지를 출력하며 False 값을 리턴하게 하겠습니다.


완성된 코드를 보면 아래와 같습니다.

Stack 자료구조 코드 확인하기


일부로 파이썬에서 기본적으로 제공하는 pop() 기능을 이용하지 않고 Stack 자료구조의 pop기능을 구현하였습니다.


추가적으로 궁금한 사항은 댓글에 남겨주세요 :)

블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc