이중연결리스트
-
1. Linked List ADTs Linked List를 ADT(Abstract Data Types)로 만들어 볼 것입니다. 참고로 파이썬의 리스트라고 하는 자료구조는 링크드리스트입니다! 그래서 생각해 보시면 다른 언어와 달리 파이썬에서 리스트(다른 언어의 배열)를 선언할 때는 그 크기를 지정하지 않고도 원소를 삽입하는 것을 아실 수 있습니다. 그래서 다른 언어의 배열에서 특정 인덱스에 접근하는 것은 random access이기 때문에 시간 복잡도가 O(1)이지만 파이썬에서는 노드를 타고 쭉 가기 때문에 O(N)의 시간복잡도를 갖습니다. 그렇다면 이제 링크드리스트에 대해서 알아볼까요? 2. Singly linked lists (단일 연결 리스트) 중요한 컨셉 head node: 리스트에서 가장 앞에 있..
[자료구조와 알고리즘 | 파이썬] Linked List(연결 리스트) | Singly linked list(단일 연결 리스트)와 Doubly linked list(이중 연결 리스트)1. Linked List ADTs Linked List를 ADT(Abstract Data Types)로 만들어 볼 것입니다. 참고로 파이썬의 리스트라고 하는 자료구조는 링크드리스트입니다! 그래서 생각해 보시면 다른 언어와 달리 파이썬에서 리스트(다른 언어의 배열)를 선언할 때는 그 크기를 지정하지 않고도 원소를 삽입하는 것을 아실 수 있습니다. 그래서 다른 언어의 배열에서 특정 인덱스에 접근하는 것은 random access이기 때문에 시간 복잡도가 O(1)이지만 파이썬에서는 노드를 타고 쭉 가기 때문에 O(N)의 시간복잡도를 갖습니다. 그렇다면 이제 링크드리스트에 대해서 알아볼까요? 2. Singly linked lists (단일 연결 리스트) 중요한 컨셉 head node: 리스트에서 가장 앞에 있..
2022.12.31 -
이번 시간에는 LinkedList의 종류 중에서 Double LinkedList에 대해서 알아 보겠습니다. 1. Doubly Linked List(이중 연결 리스트)란? 이전 내용에 있는 LinkedList는 앞에 'Single'이 생략 되어있는 셈이라 생각하면 됩니다. 그럼 무엇이 single이고 무엇이 double일까요? 위 그림은 Double LinkedList의 대략적인 구조를 나타낸 그림입니다. 아래 그림을 보면, LinkedList와는 다르게 한 노드에서 다른 노드를 가리키는 pointer가 양방향으로 있습니다. 즉, 다음 노드를 가리키는 next pointer 말고도 이전노드를 가리키는 prev pointer 하나가 더 추가 된 것입니다. 이것이 LinkedList와는 구분되는 Double ..
[자료구조 | Java] Double LinkedList(이중 연결 리스트)이번 시간에는 LinkedList의 종류 중에서 Double LinkedList에 대해서 알아 보겠습니다. 1. Doubly Linked List(이중 연결 리스트)란? 이전 내용에 있는 LinkedList는 앞에 'Single'이 생략 되어있는 셈이라 생각하면 됩니다. 그럼 무엇이 single이고 무엇이 double일까요? 위 그림은 Double LinkedList의 대략적인 구조를 나타낸 그림입니다. 아래 그림을 보면, LinkedList와는 다르게 한 노드에서 다른 노드를 가리키는 pointer가 양방향으로 있습니다. 즉, 다음 노드를 가리키는 next pointer 말고도 이전노드를 가리키는 prev pointer 하나가 더 추가 된 것입니다. 이것이 LinkedList와는 구분되는 Double ..
2022.12.27