728x90
반응형
이중 연결 리스트
-
[JS] 연결 리스트자료구조와 알고리즘 2022. 8. 9. 21:43
추가와 삭제가 반복된다면 연결 리스트를 사용하자 연결 리스트란? 각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다. 데이터 필드 = 데이터 영역 = 데이터 저장 링크 필드 = 포인터 영역 = 다른 노드의 주소 값을 저장 특징 메모리가 허용하는 한 요소를 제한 없이 추가할 수 있다. 배열과 차이점 1. 메모리 차이 배열은 순차적인 데이터, 즉 메모리 영역이 연속적으로 사용된다. 연결 리스트는 각 데이터가 퍼져있다. 즉, 포인터를 사용하여 각 영역을 참조한다. 2. 요소 삭제 / 추가 배열 배열은 O(n) 시간 소요 연결 리스트 삭제 1. 삭제하려고 하는 요소를 지정 2. 삭제하려고 하는 요소의 전 요소의 포인터를 삭제하려고 하는 요소..