[HUFS/자료구조] #6 연결 리스트

연결 리스트

그동안 배열에 index를 넣는 구조로 자료 구조를 구현했었는데,,

연결 리스트는 물리적으로 흩어진 데이터들의 노드를 링크로 연결해 사용한다!

 

링크 정보를 따라서 다음 노드를 찾아가는 구조

배열과 달리 용량이 고정되지 않아 효율적이다!

중간에 삽입/삭제 시간 복잡도는 O(1), 접근(순회)할 때 시간 복잡도는 O(n)이다

노드는 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성

연결 리스트의 시작점을 헤드 포인터가 가리키고 마지막 링크 필드는 None 혹은 NULL

끝 노드를 시작점에 연결하는 원형 연결 리스트나 앞 노드의 정보도 저장하는 이중 연결 리스트

연결된 스택

노드와 연결된 스택 생성자

삽입 / 노드를 만들고 top(헤드 포인터)이 노드를 가리키게 함

삭제 / 링크 데이터를 넘겨주고 데이터 반환

None 까지 전체 노드를 순회

단순 연결 리스트

연결된 스택과 동일한 구현 (top -> head)

pos 번째 노드를 찾아 데이터 반환

삽입 연산

삭제 연산

단순 연결 리스트 테스트 프로그램

연결된 큐

연결된 큐 클래스

삽입 연산 enqueue()

삭제 연산 dequeue()

전체 노드 순회

원형 큐 테스트 프로그램

이중 연결 리스트

단순 연결 리스트로 덱을 구현할 때 삭제시 앞 주소를 알 수 없는 문제 발생

이중 연결 리스트를 사용해 해결

연결된 덱 클래스

Front/Rear 노드 삽입

Front/Rear 노드 삭제