목록Computer Science/Data Structure (12)
without haste but without rest
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/Jmtec/btqBHy1duim/zGOu48kcspnoo52GBUthj0/img.png)
더블 링크드 리스트(Doubly Linked List) 더블 링크드 리스트는 포인터가 다음 주소 뿐만 아니라 이전 주소도 갖는다. 링크드 리스트 구조에서 이전 주소값을 저장할 멤버를 추가로 만들어주면 된다. class Node: def __init__(self, data, prev = None, next = None): self.data = data self.prev = prev self.next = next class DLinkedList: def __init__(self): self.head = None def insert(self, data): if self.head == None: self.head = Node(data) else: node = self.head while node.next: no..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cH9LSE/btqBFNxzGBa/c0jNcLqNH0hQvl9McuCC0K/img.png)
링크드 리스트(Linked List) 배열은 정해진 공간에 데이터를 순차적으로 적재한다. 반면, 링크드 리스트는 노드가 다음 노드(데이터)의 주소값을 가지고 있다. 따라서 배열이 공간의 크기를 미리 할당 해줘야 한다는 단점을 해결할 수 있다. 단, 저장 측면에서는 비효율적이다. 구조 노드(Node): 데이터를 저장하는 단위 (데이터와 포인터로 구성) 포인터(Pointer): 각각의 노드 안에서 다음 노드의 주소(위치)를 가짐 위 이미지에서 정사각형 두개가 붙은 구조가 하나의 노드이고, 화살표가 포인터다. 즉 여러개의 노드들이 연결된 구조다. class Node: def __init__(self, value): self.value = value self.next = None class LinkedList:..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/dUXaw0/btqBGe9vJ0m/Cughuy1yI8NDhcAfWzUUe1/img.png)
스택(Stack) 스택은 푸쉬와 팝이라는 두가지 행위가 존재한다. Push: 데이터 인풋 Pop: 데이터 아웃풋 1. 가장 먼저 삽입한 데이터가 가장 마지막에 출력된다. 2. LIFO (Last-In, First-Out) 구조 # Stack class Stack: def __init__(self): self.stack_list = [] def push(self, data): self.stack_list.append(data) def pop(self): if self.stack_list == []: return False else: res = self.stack_list[-1] del self.stack_list[-1] return res # Test Code myStack = Stack() for a i..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bowrE6/btqBFuSuPPG/rh7hRhJ5qMKeCJoVRBUFM0/img.png)
큐(Queue) 큐는 엔큐(Enqueue)와 디큐(Dequeue)로 구성 Enqueue: 데이터 인풋 Dequeue: 데이터 아웃풋 1. 가장 먼저 삽입한 데이터가 가장 먼저 출력 ex) line up 2. FIFO (First-in First-out), LILO (Last-in Last-out) 구조 3. 멀티 태스킹을 위한 프로세스 스케쥴링 방식 구현에서 자주 사용 # Queue class Queue: def __init__(self): self.queue_list = [] def enqueue(self, data): self.queue_list.append(data) def dequeue(self): if self.queue_list == []: return False else: res = self..