자바 자료구조2 -이중 연결리스트(LinkedList)

1. 단일 연결리스트의 한계 단일 연결리스트는 결국 한방향으로만 이동할 수 있다는 한계점이 있어서 다른 방향으로 탐색하는 것이 불가능하다 때로는 다른 방향으로도 탐색하고 싶을 수 있는데 이런 문제를 해결하기 위해 next를 확장해서 특정 노드의 뒷 노드만 이어주는 것이 아니라, 앞 노드까지 이어질 수 있도록 한다. 2. 이중 연결리스트 단순히 단일 연결리스트에 새로운 노드로 prev를 추가한 것 뿐이다. 이중 연결리스트 역시 단일 연결리스트와 마찬가지로 삽입, 삭제, 탐색이 모두 가능하다. 탐색은 방향성이 양쪽에서 있다고는 하지만 어쨌든 일일이 확인해야하므로 O(N) 하지만 삽입, 삭제의 경우 해당하는 위치를 알고있다면 그냥 선을 끊고 연결해주는 작업만 하면 되므로 O(1) 이때 이중연결리스트는 한방향이..