목록NEXT (1)

대학생 쩡딱구리

4-4. 양방향 연결 리스트

한방향 연결 리스트는 연결 구조가 비대칭이라 임의의 노드의 삭제가 아주 비효율적이다. 즉, 아래의 단점을 갖는다. 해당 노드의 레퍼런스를 알아도 삭제에 O(n)의 시간 복잡도를 갖는다. 삭제를 하려면 삭제할 노드뿐만 아니라 이전 노드의 레퍼런스가 필요한데, 항상 head부터 해당 노드의 이전 노드까지 이동하는 시간이 필요하다. 연결 리스트가 대칭성을 갖도록 이전 노드와 다음 노드의 레퍼런스를 갖도록 해보자. 1. 양방향 연결 리스트 양방향 연결 리스트(Doubly Linked List)는 노드들이 양방향으로 연결된 리스트로, 각 노드들은 객체(element), 이전 노드(prev), 다음 노드(next)의 레퍼런스를 저장한다. 이때 링크를 따라 특정 노드의 데이터를 접근하고 수정한다. 양방향 연결 리스트..
STUDIES/DATA STRUCTURE 2020. 10. 22. 10:33
이전 Prev 1 Next 다음