연결구조, 환형 연결리스트, 이중 연결리스트, 환형 이중 연결리스트

환형 연결리스트

 

개요

연결리스트의 제한성(어떤 특정 노드의 선행 노드를 찾기 위해 head부터 시작)을 해결하기 위한 자료구조

• 마지막 노드의 연결필드가 NULL이 아닌 첫 번째 노드의 주소를 가짐
• 한 노드에서 모든 노드로의 접근이 가능함
• LINK를 따라 계속 순회하면 이전 노드에 접근이 가능함
• 삽입과 삭제가 용이함
• 탐색 시 무한반복이 발생함 - 헤드노드로 보완
• 리스트 전체를 가용공간 리스트에 반환할 때 리스트의 길이에 관계없이 일정 시간에 반환할 수 있음

연결리스트

 

환형 연결리스트의 ADT

ADT CircularLinkedlist
데이터
0개 이상의 노드를 가진 유한순서 리스트(Element는 데이터 값)
연산자 및 연산내용 // CL∈CLinkedlist, n∈node, p∈position
CLlinkedlist() //환형 연결리스트를 생성
~CLlinkedlist() //환형 연결리스트를 소멸
Boolean search(CL, n) //환형 연결리스트에서 주어진 노드를 탐색
CLinkedlist insert(CL, n) //환형 연결리스트에 주어진 노드를 삽입
CLinkedlist remove(CL, n) //환형 연결리스트에서 주어진 노드를 삭제
remove_all(CL) //환형 연결리스트의 모든 노드를 삭제
Element get_data(CL, p) //p가 가리키는 현재 노드의 데이터를 출력
Element get_nextnode(CL, p)//p가가리키는현재노드의다음노드를출력
Element display() //환형 연결리스트의 모든 노드를 출력
End CircularLinkedlist

 

환형 연결리스트 삽입/삭제

 

노드의 삽입/삭제

삽입 알고리즘(첫번째로)

 

GitHub - dlfrnaos19/algorithm_with_c: learning algorithm

삽입 알고리즘(첫번째로 삽입, CL = 공백 리스트)

삽입 알고리즘(첫 번째로 삽입, CL != 공백리스트)

삽입 알고리즘(첫 번째로 삽입, CL != 공백 리스트)

 

삭제 알고리즘

 

GitHub - dlfrnaos19/algorithm_with_c: learning algorithm

삭제 알고리즘(포인터 pre가 가리키는 노드의 다음 노드를 삭제)

삭제 알고리즘(포인터 pre가 가리키는 노드의 다음 노드를 삭제)