datastructure2 # 3. 단방향 연결 리스트 (Single Linked List) 지난 포스트에서는 데크에 대해서 다루었다. 데크의 직접 구현 부분에서는 연결 리스트를 사용하여 구현했다. 그래서 실은 순서가 뒤집히지 않았나 싶지만.. collections 라이브러를 통해서도 데크를 사용할 수 있기에 이번 포스트를 읽고 지난 포스트를 다시 보기를 권장한다. 각설하고, 이번 포스트에서는 연결 리스트에 대해서 다루겠다. 연결리스트의 키워드를 세 가지 뽑으라면 필자는 이렇게 말할 것이다. 노드, 삽입, 수정 리스트나 스택, 큐에서는 보관하고 있는 데이터가 raw data (원시 데이터 - 이를테면, 정수형) 였다. 하지만, 연결 리스트에 사용되는 데이터의 (클래스) 타입은 Node 이다. 왜 굳이 클래스를 사용하는가? 그것은 단순히 원시 데이터 이외에도 다음 노드를 가르킬 포인터(next)가.. 2021. 12. 3. # 2. 데크 (Deque) 저번 포스트에서는 나서스의 스택에 스택과 큐에 대해 알아보았다. 이번 포스트에서는 큐의 연장선상 개념(?)인 데크에 대해서 알아보겠다. 데크는 풀네임 영어로 Double Ended Queue를 의미한다. 즉, 양방향으로 끝이 존재하는 큐를 뜻한다. 이번에도 역시 그림을 그려보자. 큐와 모양 자체는 똑같다! 하지만, 큐는 한뱡으로 들어가고 나갈 수 없는 방면에 데크는 양끝에 데이터가 들어오고 나갈 수 있는 특징이 있다. 그렇다면 데크를 왜 사용하는지 알아보자. 이는 파이썬의 리스트 자료형과 비교하면 알 수 있다. 우리가 리스트에 insert하는 과정을 그림으로 그리면 다음과 같다. 먼저 insert를 하기 위한 공간 하나를 할당해주어야 한다. 그 다음 기존에 존재하던 자료의 갯수(N개, 위 그림에서는 2개.. 2021. 12. 2. 이전 1 다음
