728x90
연결리스트(Linked_List)
- 동적으로 크기가 변할 수 있고, 삭제/삽입 시 데이터를 이동할 필요가 없는 연결된 표현(linked representation)
- 데이터를 한 군데 모아두지 않고, 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법
- 포인터(pointer)를 통해 데이터를 연결
연결리스트에서 각각의 원소(element)를 노드(node)라고 한다.
노드는 데이터와 뒤쪽 노드를 가리키는(참조하는) 포인터(pointer)를 가지고 있다.
맨 앞 노드를 head node 맨 뒤를 tail node 라고 한다.
또 각 노드에서 바로 앞쪽 노드를 predecessor node 바로 뒤쪽 노드를 successor node 라 한다.
자신과 같은 형의 인스턴스를 참조하는 필드가 있는 구조를 자기참조(self-referential)형이라고 한다.
장단점
- 장점
- 삽입/삭제가 보다 용이
- 연속된 메모리 공간이 필요하지 않다.
- 크기 제한이 없다
- 단점
- 구현이 어렵다
- 오류가 발생하기 쉽다
- 포인터도 저장해야하기에 메모리 공간을 많이 사용한다.
Node의 필드
- data - 데이터
- Next - 뒤쪽 포인터
함수
- search() - 검색수행 - 선형검색
- add_first() - 머리에 노드 삽입
- add_last() - 꼬리에 노드 삽입
- remove_first() - 머리 노드 삭제
- remove_last() - 꼬리 노드 삭제
- 리스트에 노드가 하나라면 remove_first() 함수를 호출한다.
- remove() - 임의의 노드 삭제
- remove_current_node() - 주목 노드 삭제
- clear() - 모든 노드 삭제
- next() - 주목 노드를 한칸 뒤로 이동
- print_current_node - 주목 노드 출력
- print() - 모든 노드 출력
프리리스트(free list)
- 삭제된 레코드 그룹을 관리할 때 사용한다. 삭제후 비어있는 배열의 문제 해결이 가능하다.
Node클래스 Node에 추가된 필드
- dnext - 프리리스트 뒤쪽 포인터(프리리스트 뒤쪽을 참조하는 커서)
Array LinkedList에 추가된 필드
- deleted - 프리리스트의 머리노드를 참조하는 커서
- max - 배열에서 맨끝쪽에 저장되는 노드의 레코드 번호
이중 연결리스트(Doubly LinkedList)
- 각 노드에 뒤쪽 노드와 앞족 노드에 대한 포인터가 주어진다.
노드의 필드
- data - 데이터에 대한 참조
- prev - 앞쪽 노드에 대한 참조
- next - 뒤쪽 노드에 대한 참조
원형 이중 연결리스트(Circular doubly LinkedList)
- 원형 리스트와 이중 연결 리스트를 결합
728x90