Computer Science/자료구조

[자료구조] 양방향 연결리스트(Doubly Linked List), 원형 양방향 연결리스트(Circularly doubly Linked List)

목표 단방향 연결 리스트에 이어 양방향 연결리스트에 대해서 알아보도록 하겠습니다. 목차 클릭하면 해당 목차로 이동합니다. 양방향 연결 리스트(Doubly Linked List) 원형 양방향 연결 리스트(Circularly Doubly Linked List) 양방향 연결 리스트 연산(이동·삽입·탐색·삭제) 및 파이썬 코드로 구현하기 정리 개요 이전 포스팅에서 단방향 연결 리스트(Singly Linked List)에 대해서 알아보았습니다. 연결 리스트를 관리하는 클래스와 각 노드들의 head부터 tail까지 다음 노드의 주소와 key(value)값을 갖고 있는 구조입니다. 참고 : [자료구조] 단방향 연결리스트(Singly Linked List)란? 파이썬으로 구현하기 다음 노드의 주소만 알고 있기 때문에,..

[자료구조] 단방향 연결리스트(Singly Linked List)란? 파이썬으로 구현하기

목표 단방향 연결리스트의 개념에 대해서 이해해보고 파이썬으로 구현해보도록 하겠습니다. 목차 클릭하면 해당 목차로 이동합니다. 단방향 연결 리스트란?(Singly Linked List) 파이썬으로 구현하기 정리 개요 앞서 순차적 자료구조인 리스트와 배열에 대해서 이해하고 스택과 큐에 대해서 공부하고 예제를 풀어보았습니다. 이번 포스팅에서는 단방향 연결리스트에 대해서 알아보도록 하겠습니다. 연결리스트는 배열과 유사하지만, 연속된 공간에 메모리를 차지하고 인덱스를 통해 상수시간 내에 값을 처리한다는 특징이 있습니다. 반면, 연결리스트는 메모리 상에 흩어져 있지만 연결되어 있다는 특징이 있습니다. 이에 대한 부분을 자세히 알아보도록 하겠습니다. 단방향 연결 리스트란?(Singly Linked List) 연결리스..

[자료구조] 큐(Queue)란?

목표 순차적 자료구조인 큐의 개념에 대해서 알아보겠습니다. 개요 저번 포스팅에서는 순차적 자료구조인 스택에 대해서 알아보았습니다. 큐(Queue)는 스택과 비슷한 부분들이 많기 때문에 비교하면서 큐에 대해서 이해하는 시간을 갖도록 하겠습니다. 큐(Queue)란? 큐(Queue)는 스택과 비슷한 형태를 가집니다. 다만, 스택은 LIFO(Last In First Out) 구조로 마지막에 들어온 데이터가 제일 먼저 나가는 형태입니다. 큐는 FIFO(First In First Out) 구조로 맨 처음 들어온 데이터가 먼저 나가는 형태입니다. 예를 들어, 마트에서 줄 서는 것을 생각할 수 있겠네요. 스택에서는 Push, Pop, Len, Top 4가지 연산을 지원했습니다. 큐는 Enqueue, Dequeue, i..

[자료구조] 스택 예제, 중위 표기(infix)를 후위 표기(postfix)로 변환하기

목표 스택을 활용해서 중위 표기법으로 입력한 연산을 후위 표기법으로 변환해서 결과를 출력하는 프로그램을 작성해보겠습니다. 목차 클릭하면 해당 목차로 이동합니다. 수식 표기법 스택 예제 : 중위 표기법을 후위 표기법으로 변환하여 계산하는 계산기 정리 개요 저번 포스팅에서 스택에 대해서 복습했습니다. 스택은 LIFO(Last In First Out) 구조를 갖는 자료구조입니다. 마치 접시와 같이 마지막에 들어간 데이터가 맨 처음 나오는 구조로, 파이썬의 클래스를 활용해서 구현했습니다. 클래스 안에 멤버 리스트를 생성해서 append, pop 함수로 스택을 만들었습니다. 이번 포스팅에서는 스택을 활용해서 중위 표기(infix)로 입력된 수식을 후위 표기(postfix)로 바꾸고 계산하는 프로그램을 작성해보도록..