연결리스트(linked list)

배열의 단점을 개선하기 위해 생긴 자료구조

 

연결 리스트 / Linked List는 C언어에서 중요한 데이터 구조였는데 파이썬은 리스트에서 연결 리스트의 모든 기능을 지원한다.

연결 리스트 기본 자료구조

• Node: 데이터와 데이터 주소(Pointer)로 이루어져있다.
• Head: 시작 데이터
• Tail: 마지막 데이터
• Next = None(또는 Null): 다음 데이터가 없을 경우 데이터 주소(Pointer) 값이 None 또는 Null이다.

 

장점

• 배열은 미리 데이터 공간을 할당해야하는데 연결리스트는 미리 할당 할 필요가 없다. (유동적으로 데이터 추가 및 삭제가 가능)
• 연결 리스트 수정 시 시간복잡도 O(1)을 갖는다. (항상 일정한 속도)

단점

• 다음 데이터를 연결하기 위해선 주소(Pointer) 공간이 필요하다. (저장공간 효율이 높지 않다)
• 연결 리스트 경우, 중간에 데이터 추가, 삭제 시 인덱싱을 다시 해줘야한다.