목록2022/09/07 (1)

넘치게 채우기

[자료구조] 1-3. 이중 연결리스트, 원형 연결 리스트(Doubly Linked List, Circular Linked List)

이중 연결 리스트 이중 연결 리스트는 기존의 연결리스트와는 달리, 쌍방향으로 연결이 되어있다. 이미 한 노드를 지나쳐도, 돌아갈 수 있다. 장점 찾아야 하는 값이 tail쪽에 가까울 때, head부터 시작해서 탐색하는 번거로움 등을 없앨 수 있다. 위치를 모르는 상태에서 값을 찾을 때에도, 앞에서 절반, 뒤 끝에서 절반씩 탐색하면 훨씬 효율적이다. 단점 변수를 3개 사용한다.(이전 메모리주소, 내 엘리먼트, 다음 메모리주소) 이 과정에서 메모리를 더 사용하게된다. 구현이 복잡해진다. 그러나, 이런 단점들을 두고도, 얻게 되는 것이 많아서, 실제 연결리스트를 사용할 때, 이중 연결리스트를 많이 사용한다. 노드의 추가 노드 a↔b↔d에서 b↔d 사이에 c를 연결하고 싶으면, c의 다음 노드로 d를 연결해주고..
컴퓨터과학/자료구조 2022. 9. 7. 23:40
이전 Prev 1 Next 다음