1. Linked List ADTs Linked List를 ADT(Abstract Data Types)로 만들어 볼 것입니다. 참고로 파이썬의 리스트라고 하는 자료구조는 링크드리스트입니다! 그래서 생각해 보시면 다른 언어와 달리 파이썬에서 리스트(다른 언어의 배열)를 선언할 때는 그 크기를 지정하지 않고도 원소를 삽입하는 것을 아실 수 있습니다. 그래서 다른 언어의 배열에서 특정 인덱스에 접근하는 것은 random access이기 때문에 시간 복잡도가 O(1)이지만 파이썬에서는 노드를 타고 쭉 가기 때문에 O(N)의 시간복잡도를 갖습니다. 그렇다면 이제 링크드리스트에 대해서 알아볼까요? 2. Singly linked lists (단일 연결 리스트) 중요한 컨셉 head node: 리스트에서 가장 앞에 있..

이번 시간에는 LinkedList의 종류 중에서 Double LinkedList에 대해서 알아 보겠습니다. 1. Doubly Linked List(이중 연결 리스트)란? 이전 내용에 있는 LinkedList는 앞에 'Single'이 생략 되어있는 셈이라 생각하면 됩니다. 그럼 무엇이 single이고 무엇이 double일까요? 위 그림은 Double LinkedList의 대략적인 구조를 나타낸 그림입니다. 아래 그림을 보면, LinkedList와는 다르게 한 노드에서 다른 노드를 가리키는 pointer가 양방향으로 있습니다. 즉, 다음 노드를 가리키는 next pointer 말고도 이전노드를 가리키는 prev pointer 하나가 더 추가 된 것입니다. 이것이 LinkedList와는 구분되는 Double ..

이번 포스팅은 지난 포스팅에 이어 ArrayList에서 했던 것과 마찬가지로 LinkedList에서의 데이터 삽입, 데이터 삭제, 리스트 검색 등의 기능에 대해서 다뤄보도록 하겠습니다. 1. 연결리스트(Linked List)란? LinkedList는 Node라는 객체로 이루어져 있는데 Node는 데이터를 저장하는 field와 다음 노드를 가리킬 수 있는 next pointer field로 구성이 되어있습니다. 이말인 즉슨, 이 노드들이 연결된 형태의 자료구조를 바로 LinkedList라고 하는 것입니다. 예를 들어, 학교에서 어느 반의 모든 학생들의 데이터를 저장한다고 했을 때, 학생 한명 한명의 신상정보 자료를 노드로 만들고, 1번 학생의 신상정보 자료에 2번 신상정보 자료가 어디 있는 지 표시를 해 ..

첫번째 자료구조로 가장 간단한 형태의 리스트에 대해서 배워보겠습니다. 1. 리스트란? 리스트는 선형적인 자료구조 중의 하나로서 데이터를 일렬로 늘여 놓은 형태입니다. 그렇기 때문에 리스트는 순서를 가진다는 특징이 있습니다. 모든 언어를 사용하든 간에 가장 기본적으로 배우게 되는 메모리 공간 형태이며 자료형(Data Type)이 둘 이상의 값을 저장할 수 있습니다.(다만, Python은 예외) 이곳에서는 리스트를 어떻게 생성하고 어떻게 사용하는 지 보다는 리스트라는 자료구조에서 데이터를 어떻게 다루는 지에 대해 더 알고 싶기 때문에 이번 챕터에서는 리스트를 관리를 할 때 중요한 기능 3가지를 다루어 보겠습니다. 데이터 삽입하기 데이터 삭제하기 리스트 탐색하기 이 3가지는 어떤 데이터 구조를 다룰 때도 항상..