연결리스트(List - 종류/정의/시간 복잡도)

20190507 - 시간복잡도 추가

1. 연결리스트란

데이터 필드, 링크 필드로 구성되며, 자료 중간에 삽입이 쉬운 자료구조

데이터 이외에 링크 필드도 필요하므로 메모리가 더 소요된다

배열에 비해 삽입, 삭제가 간편하다

 

2. 연결리스트의 종류

2.1 단순 연결 리스트

- 헤드 포인트를 가진다

- 마지막 노드의 링크는 NULL을 참조한다

 

2.2 이중 연결 리스트

- 데이터 필드 하나와 두개의 링크 필드를 가진다.

 

2.3 원형 연결 리스트

- 단순 연결 리스트의 마지막 노드의 링크 필드를 헤드로 가르치면 원형 연결 리스트가 된다.

 

3. 시간 복잡도

- 일반 배열은 배열 삽입/삭제 하는데 O(n)이 드는 방면, 리스트는 O(1)에 가능

- 링크 필드만 재연결 및 삭제 해주면 된다