자료구조 - Doubly Linked List

Doubly Linked List 단일 연결 리스트는 하나의 노드에 데이터와 다음 노드를 가리키는 노드만을 가지고 있었다면 이중 연결 리스트는 여기서 하나더 추가되어 이전 노드를 가리키는 노드도 추가되어 있습니다. 이중 연결 리스트가 단일 연결 리스트에 비해 좋은 점은 검색 능력입니다. 단일 연결 리스트의 경우 N 번째에 있는 노드를 검색하기 위해서는 이전 노드를 아는 경우는 O(1)의 성능을 가지지만 이전 노드를 모르는 보통의 경우에는 N만큼을 순회해야 하기 때문에 O(n)이 소요됩니다. 하지만 이중 연결 리스트의 경우 이전 노드를 참조하는 변수를 가지고 있기 때문에 단일 연결 리스트에 비해 효율적인 탐색이 가능합니다. Doubly Linked List 구현 💡 구현하고자 하는 메서드 아래 메서드는 기..
자료구조 2022. 12. 3. 18:38
1