[백엔드] 연결 리스트, 포인터로 연결하여 관리

[연결리스트, 단일 연결 리스트(Singly Linked List)]

연결리스트는 리스트 내의 요소(노드)들을 포인터로 연결하여 관리하는 선형 자료구조이다.

 

출처: https://wikidocs.net/224937

각 노드는 데이터와 다음 요소에 대한 포인터를 가지고 있다.

첫 번째 노드를 HEAD, 마지막 노드를 TAIL

연결 리스트는 메모리가 허용하는 한 요소를 계속 삽입할 수 있다. ->동적크기, 쉬운 삽입 삭제, 필요한 만큼 메모리 할당

시각 복잡도는 탐색에는 O(n), 노드 삽입과 삭제는 O(1)라는 특징을 가지고 있다.

 

배열은 순차적인 데이터가 들어가기 때문에 메모리 영역을 연속적으로 사용한다.

반면, 연결 리스트는 메모리 공간에 흩어져서 존재한다는 점에서 배열과 차이가 있다.

 

[이중 연결 리스트(Doubly Linked List, Circular Linked List)]

더블 연결의 형태인 이중 연결 리스트도 있다.

 

출처: https://velog.io/@717lumos/자료구조-연결리스트Linked-List-단일연결리스트-이중연결리스트

 

 

참고자료 및 더 자세한 정보는 https://wikidocs.net/224937

03장 파이썬으로 연결 리스트 구현하기