자료구조
-
자료 구조 한방에 정리자료구조 2020. 12. 15. 23:33
자료구조 한방에 정리 주기적으로 자료구조의 핵심 특징들을 머리에 되새김 하기 위해서 이렇게 한방에 자료구조를 정리하는 포스팅을 올린다! 목차 1. Array 2. Linked List 3. Stack 4. Queue 5. Hash Table 6. Graph 7. Tree Array Array는 물리적 주소와 논리적 주소 같은 자료구조이다. 장점 인덱스 로 접근하며 원소 접근이 O(1)로 빠르다. 구현이 쉽다. 단점 삽입, 제거시 뒤의 원소들을 앞으로 이동시켜 주어야 하므로 비용이 크다 크기가 정해져 있어 한정적이다. 원소가 삭제되면 그 자리가 비어버리므로 공간이 낭비된다. 이미지 출처: https://beginnersbook.com/2018/10/data-structure-array/ Linked Lis..
-
Doubly Linked List자료구조 2020. 10. 6. 21:38
Doubly Linked List 기존의 단순 연결리스트는 일련의 요소들을 다룰떄에 효과적이지만, 단점이 있습니다. 연결리스트를 운행할 때에 링크에 반대쪽으로 운행할 필요가 있을 경우에도 항상 연결리스트 첫 노드로 이동한 후 운행을 다시 시작하는 불편함이 있습니다. 그러나, 이중 연결 리스트는 이러한 단점을 없애기 위해서 노드에 prev 에 이전 노드를 참조하도록 합니다. Node Class class Node: """ 가볍고, 논퍼블릭한 이중 연결 리스트 노드 """ __slots__ = '_element', '_prev', '_next' def __init__(self, element, prev, nxt): self._element = element self._prev = prev self._next..
-
Singly Linked List자료구조 2020. 10. 3. 01:07
Singly Linked List 싱글 링크드 리스트는 선형구조 형태인 노드들의 집합입니다. 각 노드는 시퀀스의 요소인 객체에 대한 참조를 저장합니다. 자신의 다음 노드를 참조( next )합니다. 싱글 링크드 리스트의 첫번째와 마지막 노드는 head 와 tail 입니다. head 먼저 시작해서 각 노드에 참조에 따라 다른 노드로 이동하면서 최종적으로 tail노드에 도달할 수 있습니다. 일반적으로 이 프로세스를 Linked List traversing 이라고 합니다. 노드의 next 참조가 다른 노드에 대한 링크 또는 포인터 로 보여질 수 있기 떄문에, 리스트 traversing 처리는 link hopping 또는 pointer hopping 이라고 합니다. 싱글 링크드 리스트 헤드 요소 삽입 싱글 링크..
-
Double-Ended Queue자료구조 2020. 9. 30. 13:34
Double-Ended Queues 더블 엔디드 큐는 기존 큐 자료구조 형태에서 큐의 앞,뒤로 삽입,삭제가 이루어질 수 있도록 구현한 자료구조입니다. The Deque Abstract Data Type Deque ADT는 다음 메서드를 다룹니다. D.add_first(e): 데크 앞에 요소를 추가합니다. D.add_last(e): 데크 뒤에 요소를 제거힙니다 D.delete_first(e): 데크 앞에 요소를 제거합니다. D.delete_last(e): 데크 뒤에 요소를 제거합니다. 추가적으로, 데크는 다음 접근 메서드를 포함합니다. D.first(): 데크 앞의 요소를 반환합니다. D.last(): 데크 뒤의 요소를 반환합니다. D.is_empty(): 데크가 비었을 경우 True를 반환합니다. len..
-
Queue자료구조 2020. 9. 30. 12:31
Queue 큐는 또다른 기능적 자료구조입니다. 쉽게 스택의 "사촌"과 비슷합니다. 큐는 First-in, First-out (FIFO) 원리에 따라 삽입과 제거되는 객체들의 모임입니다. 요소는 자유롭게 삽입될 수 있습니다. 그러나, 요소는 가장 오래 머물렀던 요소 부터 제거됩니다. 큐 추상적 데이터 타입은 객체를 순서대로 유지하는 집합을 정의합니다. 요소의 접근 또는 삭제는 큐의 처음 요소로 제한되고 요소의 삽입은 큐 순서의 가장 마지막으로 제한됩니다. 큐 추상적 데이터 형식(ADT)는 두가지 메서드를 다룹니다. Q.enqueue(e): 큐의 마지막에 요소를 추가합니다. Q.dequeue(): 큐의 가장 앞 요소를 제거하고 반환합니다. 큐가 비었을 때, 에러가 발생합니다. 큐 ADT는 또한 다른 메서드도..
-
Stack자료구조 2020. 9. 27. 23:37
Stack 스택은 Last-in,First-out(LIFO) 원리에 따라 삽입과 제거되는 객체들의 모임입니다. 스택은 pushing과 poppping 기능적 연산을 통헤 삽입과 제거를 합니다. 실제 사용되는 사례 인터넷 웹브라우저는 가장 최근에 방문한 주소를 저장합니다. 유저가 새로운 사이트에 방문할 때마다, 스택에 주소가 "PUSHED" 됩니다. 브라우저는 유저가 "back" 버튼을 누를때 가장 최근 방문한 주소가 "POP" 됩니다. Stack 추상적 데이터 타입 스택은 모든 자료구조에서 가장 단순하지만 중요합니다. 스택은 추상 자료타입(ADT)입니다. 추상적 자료 타입(Abstract _Data Type)이란? 추상적 자료형은 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명시에 놓은 것입니다...