본문 바로가기

반응형

IT/자료구조

(3)
[Golang] 채널로 큐(Queue)를 만들어보자! 이번에는 번외 프로젝트로 큐를 만들어보도록 하자. 이 프로젝트를 통해 Golang의 채널(chan)이라는 연산자/자료형이 갖는 성질을 터득해볼 수 있다. 소스 코드는 아래와 같다. 우리는 5칸 짜리 큐를 만들고, 1, 2, 3을 차례대로 넣었다가 Pop 시킬 것이다. // making queue with Go channel package main import "fmt" type Queue struct { item chan int } // save inputs func (q *Queue) Append(val int) { q.item
[Python] 더블 링크드 리스트 (이중 연결 리스트) 싱글 링크드 리스트를 배웠으면 더블 링크드 리스트를 빼먹을 수 없다. (만약 지난 싱글 링크드 리스트가 궁금하다면? 2019/11/29 - [IT/자료구조] - [Python] 싱글 링크드 리스트 (단순 연결 리스트)) 이 또한 워낙 방대한 자료가 많지만, 추후 그래프나 트리 구현을 할 때 제반 지식이 될 수 있도록 꼭 구현해보는 것을 추천한다. 기초적인 지식 1. 시간복잡도 Double Linked List 최선 최악 삽입 O(1) O(1) 삭제 O(1) O(1) 탐색 O(k) O(k) [인덱스 탐색 시] O(N) [값 탐색 시] 이전 포스트였던 싱글 링크드 리스트와는 다른 점이 있다면 탐색이다. 그리고 지난 싱글 링크드 리스트와 함정 또한 공유한다. 2. 장점 싱글 링크드 리스트와 모든 장점을 공유한..
[Python] 싱글 링크드 리스트 (단순 연결 리스트) 아마 자료구조를 공부하면 처음 구현하게 될 싱글 링크드 리스트. 워낙 자료도 방대하고 기구현된 소스코드가 많지만, 그만큼 기초는 중요하기에 직접 구현하면서 지식을 익혀보는 것이 낫다. 개인적인 생각이지만, 아주 기초적인 노드의 활용 방식을 몸소 익힐 수 있다는 점만으로도 단순 연결 리스트의 구현은 해볼 가치가 있다고 생각한다. 기초적인 지식 1. 시간복잡도 Single Linked List 최선 최악 삽입 O(1) O(1) 삭제 O(1) O(1) 탐색 O(k) O(N) ※ 단, 함정 있음. (아래 단점 항목 참고) 2. 장점 삽입과 삭제가 O(1)에 이루어진다. 삽입과 삭제를 할 때마다 동적으로 링크드 리스트의 크기가 결정되므로 전통적인 배열(Array)에 비해 처음부터 큰 공간을 할당할 필요가 없어진다..

반응형