자료구조 이중 연결 리스트(Double Linked List) 자바로 구현
1. 개요 연결 리스트는 "노드" 에 객체를 담고, 포인터를 통해 연결되어있다. 단일 연결 리스트는 next 포인터로 앞으로 밖에 갈 수 없지만, 이중 연결 리스트는 prev, next 포인터 가 있어서 뒤로도 갈 수 있다. 단일 연결 리스트로 가장 마지막에 데이터를 넣으려면 처음부터 포인터를 타고 가야 하므로, 데이터가 100개면 100번, 1억개면 1억번 이동을 해야 하는데 이중 연결 리스트는 마지막에 tail이라는 더미 노드를 만들어놓고, 뒤로 갈 수 있기에, tail 에서 prev 포인터로 이동하면 데이터가 100만개가 있던, 1억개가 있던 1번의 동작으로 그 위치까지 이동할 수 있다. 또한, 삽입이나 삭제를 할 때도, head와 tail중, 가까운 곳에서 탐색을 시작하면, 데이터가 100만개면 ..
2022. 2. 14.
