반원 블로그

자료구조와 알고리즘의 성능을 분석하는 기법과 도구에 대해 알아봅니다. 위키독스 연재 : https://wikidocs.net/book/2868

자료구조와 알고리즘의 관계 자료구조는 자료를 구성하고 접근하는 체계적인 방법에 대한 것이라면, 알고리즘은 어떤 일을 수행하는 일련의 과정이자 단계적인 절차라 할 수 있습니다. 우리는 의도하지 않았지만 앞서 '단일 연결 리스트'와 '이중 연결 리스트'를 구현하며 삽입, 출력, 삭제, 탐색 연산을 설계했습니다. 각 연산은 우리가 설계한 단계에 맞춰 기능을 수행하므로 알고리즘이라 볼 수 있습니다. 사실상 자료구조와 알고리즘을 둘 다 만든 것이죠. 그러나 우리가 결과적으로 알고리즘을 만들었으나, 전문서적 및 분야에서 말하는 알고리즘과는 조금 차이가 있습니다. 전자는 '단계적인 절차'인 사전적 의미를 가지며, 후자는 '효율적이고 양질의 성능을 가진 단계적인 절차'를 말합니다. 그런 점에서 우리가 학습하려는 자료구..

탐색 출력과 탐색의 과정은 똑같습니다. 즉, 이 작업도 단일 연결 리스트와 동일하며 단지 head에서부터냐 tail에서부터냐로 나뉩니다. 다만 tail로 탐색해서 나온 위치(인덱스)는 초기값을 -1로 주고 진행할 때마다 1씩 감소시켜서 head로 구한 인덱스와 구분시키도록 하겠습니다.(마치 파이썬의 리스트처럼.) 코드 구현 #이중 링크드 리스트 class DLinkedList: #D_L_list에서 쓸 노드 class Node: def __init__(self, v, n = None, p = None): self.value = v #저장된 데이터 self.next = n #다음 노드 가리키는 변수 self.prev = p #이전 노드 가리키는 변수 #D_L_List에서 필요한 변수 def __init__..

삭제 삽입과 마찬가지로 삭제 또한 head를 통한, tail을 통한 삭제 2가지가 있습니다. 저장된 노드가 없을 때 당연히 삭제연산 경우에서 제외시켜야됩니다. #이중 링크드 리스트 class DLinkedList: #D_L_list에서 쓸 노드 class Node: def __init__(self, v, n = None, p = None): self.value = v #저장된 데이터 self.next = n #다음 노드 가리키는 변수 self.prev = p #이전 노드 가리키는 변수 #D_L_List에서 필요한 변수 def __init__(self): self.head = None #첫 생성시 내부에는 노드가 없으므로 self.tail = None #head로 삽입. v : 데이터 def insertN..

출력 이중 연결 리스트의 head를 통한 출력은 단일 연결 리스트와 동일합니다. 그래서 코드를 그대로 가져오겠습니다. 저장된 노드가 없을 때 그냥 없다라는 출력을 해주겠습니다. 저장된 노드가 있을 때(head) 위에서 말했든 단일 연결 리스트와 동일합니다. 코드 구현 #이중 링크드 리스트 class DLinkedList: #D_L_list에서 쓸 노드 class Node: def __init__(self, v, n = None, p = None): self.value = v #저장된 데이터 self.next = n #다음 노드 가리키는 변수 self.prev = p #이전 노드 가리키는 변수 #D_L_List에서 필요한 변수 def __init__(self): self.head = None #첫 생성시 ..

삽입 이중 연결리스트의 삽입 방법은 2가지입니다. 단일 연결 리스트처럼 head로 넣는 방법과 같은 방법으로 tail을 통해 넣는 방법. 각 상황에 따라 노드의 next와 prev값을 다음노드와 이전노드로 지정해주면 됩니다. 저장된 노드가 없는 경우(head,tail) 아무런 노드도 없는 경우는 head와 tail 값이 None입니다. 따라서 head를 통해 넣든, tail을 통해 넣든 결과가 같습니다. 코드 구현 #이중 링크드 리스트 class DLinkedList: #D_L_list에서 쓸 노드 class Node: def __init__(self, v, n = None, p = None): self.value = v #저장된 데이터 self.next = n #다음 노드 가리키는 변수 self.pre..