python/자료구조 알고리즘
양방향(원형) 연결리스트
1. 양방향 연결리스트의 특징 노드들을 한 쪽 방향으로만 연결시킨 자료구조인 한방향 연결리스트의 단점을 보완한 자료구조 한쪽으로만 이동할 수 있었던 한방향 연결리스트에 반대쪽으로 이동할 수 있게 링크를 추가해 양쪽방향으로 이동할 수 있게 만들었다. 첫 노드는 항상 dummy노드가 되어 리스트의 처음을 구분할 수 있게 한다. 2. 양방향 연결리스트의 장점 ○장점 1. 한 방향으로만 탐색해야 하는 한방향 연결리스트와 달리 두 방향으로 탐색을 할 수 있어 효율적이다. ○단점 1. 단방향 연결리스트에 비해 메모리를 많이 차지한다. 3. 양방향 연결리스트 구현 class Node: def __init__(self, key=None): self.key = key self.prev = self self.next = ..
한방향 연결리스트
1. 한방향 연결리스트의 특징 노드(node) : data정보와 다른 노드로 연결시켜주는 링크로 이루어져있는 class 노드들을 한 쪽 방향으로만 연결시킨 자료구조 가장 앞에 있는 노드를 head라고 부르며 head 노드를 통해서 한방향 연결리스트에 접근할 수 있다. 2. 한방향 연결리스트의 장단점 ○장점 1.추가 및 삽입에 용이한 자료구조이다. 2.메모리를 효율적으로 관리할 수 있다. ○단점 1.데이터를 탐색하기 위해서는 처음 head부분부터 탐색해야 하기 때문에 탐색에 비효율적이다. 3.시간복잡도 pushFront() : O(1) pushBack() : O(n) popFront() : O(1) popBack() : O(n) search : O(n) remove : O(n) 4.한방향 연결리스트 구현 ..
스택(stack)
1. 스택의 특징 가장 기본적인 자료구조라 할 수 있는 스택(stack) 스택은 LIFO(Last in First Out) 원칙을 따른다. 예를 들면 박스에 책을 놓으면 차례대로 마지막에 넣은것부터 빼내는듯 하는것과 같다. 주로 재귀 알고리즘과 실행 취소같은 작업을 할때 쓰인다. 2. 스택의 장단점 ○장점 1. 구조가 단순해서 구현하기 쉽다. 2. 삽입과 삭제의 속도가 빠르다. ○단점 1. 맨 위의 원소만 접근할 수 있다. 2. 탐색을 하려면 가장 먼저 push된 데이터부터 하나하나 꺼내서 옮겨야 한다. 3. 시간 복잡도 삽입함수 push() : O(1) 삭제함수 pop() : O(1) 가장 위에 있는 값을 return하는 함수 : O(1) 4. 스택 구현 class Stack: def __init__(..