파이썬 자료구조 - 연결된 구조

파이썬 자료구조 - 연결된 구조

728x90

1. 연결된 구조

- 연결된 구조는 흩어진 데이터를 링크로 연결해서 관리

- 각 항목들이 다음 항목을 가리키는 링크를 갖고 있다.

- 링크를 통해 각 항목들을 찾아간다.

2. 연결된 구조의 용량

- 배열의 경우 크기를 할당하고 사용하기 때문에 용량의 낭비가 생긴다.

- 연결된 구조의 경우 필요한 만큼만 할당하고, 크기의 제한이 없다.

3. 연결된 구조의 삽입과 삭제

- 배열은 항목의 삽입과 삭제를 할 때 시간 복잡도가 O(n)

- 연결된 항목은 삽입하는 위치의 링크를 끊고 새로운 항목을 추가

- n번째 항목에 접근하는데 O(n)의 시간이 걸린다.

1) 연결된 리스트의 장점

- Linked list의 길이를 동적으로 조절 가능

- 삽입, 삭제가 쉽다.

2) 연결된 리스트의 장점

- 임의의 노드에 바로 접근 불가

- 다음 노드를 추가하기 위해 추가 공간이 필요

- 역순으로 데이터 접근이 어렵다.

4. 노드(node)

- 데이터 필드와 링크 필드로 구성

- 헤드 포인터 : 시작 주소

5. 연결 리스트의 종류

- 단순 연결 리스트(큐)

- 원형 연결 리스트(원형 큐) : 맨 마지막 링크 필드가 첫 번째 데이터 필드를 가리킨다.

- 이중 연결 리스트(덱) : 데이터 필드 앞, 뒤로 링크 필드가 있어서 각 데이터를 연결한다.

728x90

from http://lch7215.tistory.com/100 by ccl(A) rewrite - 2021-10-31 15:26:36