TigerCow.Door

안녕하세요.

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



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


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



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

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

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

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



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


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

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

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

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


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


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

블로그 이미지

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 값을 리턴하게 하였습니다.


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




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

블로그 이미지

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 값을 리턴하게 하겠습니다.


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


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


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

블로그 이미지

Tigercow.Door

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

댓글을 달아 주세요

  • sonia 2018.06.17 14:48  댓글주소  수정/삭제  댓글쓰기

    안녕하세요!
    혹시 스택의 최대 크기(maxSize)를 지정할 수 있도록 구현할려면 어떻게 해야하는지 알 수 있을까요??

    • Favicon of https://doorbw.tistory.com BlogIcon Tigercow.Door 2018.06.17 14:59 신고  댓글주소  수정/삭제

      만약, class를 이용해 Stack을 객체를 만들때마다 사이즈를 다르게 지정하고 싶으시다면 __init__() 부분을 아래와 같이 작성하면 됩니다.
      class stack:
      def __init__(self, Size):
      self.stack_items=[]
      self.maxSize = Size
      여기에 추가로 수정해야 되는점은, push할때 무조건 적으로 stack에 요소를 넣어주는 것이 아니라, self.stack_items와 self.maxSize를 비교하여 현재 스택내부 아이템이 maxSize보다 같을때는 (크거나 같을때로 해도 됩니다.) 스택이 꽉차있다는 메세지를 출력하며, 요소를 넣지 못하게 해야하고 그렇지 않을때만 요소를 추가하도록 해야겠죠?

    • Favicon of https://doorbw.tistory.com BlogIcon Tigercow.Door 2018.06.17 15:00 신고  댓글주소  수정/삭제

      위에서 말씀드린 stack class는 stack객체를 만들때마다 해당 stack의 최대사이즈를 함께 넣어서 만들어주셔야하고, 만약 그게 아니라 어떤 stack객체던지 최대사이즈를 고정시키고 싶다면(예를 들면 10),
      class stack:
      def __init__(self):
      self.stack_items=[]
      self.maxSize = 10
      이런식으로 작성해주면 될 것 같습니다.

    • sonia 2018.06.17 15:10  댓글주소  수정/삭제

      맞아요! 최대사이즈를 고정시키고 싶었어요!! 감사합니다.!

  • Favicon of https://doorbw.tistory.com BlogIcon Tigercow.Door 2018.06.17 15:12 신고  댓글주소  수정/삭제  댓글쓰기

    넵 :) 열공하세요!

  • 2019.03.29 10:41  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다