자료구조 2. 링크드 리스트

리스트와 배열(C) 차이

- 크기 지정 여부가 다르다.

링크드 리스트

- 데이터 + 다음 노드에 대한 포인터

- 노드 생성 / 소멸 create / destroy

- 노드 추가 append

- 노드 탐색 GetNodeAt

- 노드 삭제 Remove

- 노드 삽입 Insert InsertNewHead

링크드 리스트의 장단점

- 포인터 때문에, 추가적인 메모리 소요

- 특정 위치에 있는 노드에 단방형 접근하여 시간도 소요가 많이됨

(N회의 조회 필요 / 반면 배열은 상수시간에 끝남

- 노드의 추가 삽입 삭제가 쉽고 빠름 / 이 부분에서 배열보다 유리

- 현재 노드에서 다음 노드를 얻는데 비용이 발생하지 않음

더블 링크드 리스트의 장단점

- 추가적인 포인터로 메모리 소요 가중

- 양방향으로 접근할 수 있기 때문에, 시간 소요 경감

- 노드의 추가 삽입 삭제가 쉽고 빠름

- 현재 노드에서 2개의 노드를 얻는 데 비용이 발생하지 않음

Product Manager 랜턴