[자료구조] 6. 연결 리스트의 응용

01. 연결 리스트의 변형

 

✅ 연결 리스트의 종류

 

단순 연결 리스트

• 하나의 링크만 있고 각각의  노드의 링크는 후행 노드만을 가리키는 구조
• 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점 발생

 

 

 

이중 연결 리스트

• 특정 노드는 선행 노드를 가리키는 링크와 후행 노드를 가리키는 링크를 가짐
• 특정 노드에서 선행 노드와 후행 노드에 간단한 프로그램 코드를 통해 접근할 수 있음

 

 

 

원형 연결 리스트

• 연결 리스트를 살펴보면 가장 마지막 노드의 링크 필드는 언제나 null 값임. 그래서 마지막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해 원형 연결 리스트가 제안됨

※ null

== 아무것도 없다

!= 0

 

예) 정수형 변수 i를 선언하면 0이 아니라 null값이 들어감

 

 

 

 

 

 

 

---

02. 원형 연결 리스트

 

• 연결리스트의 마지막 노드의 링크 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결 리스트가 제안됨

 

 

 

 

 

🔸정의 및 생성

 

 

 

🔸원형 연결 리스트의 노드 삽입

▪️ 삽입 연산

NewNode 생성

NewNode → data = x; //100
NewNode에는 주소값(7000)이 담겨있고 NewNode → data = x; 를 할당할 경우 해당 주소값으로 가서 data라는 변수에 x값을 넣어줌

 

 

함수 return 타입이 void 즉, 아무것도 반환하지 않아도 해당 함수에서 실행한 연산들은 고스란히 남아있음
왜냐면 매개변수로 포인터 변수를 공유했기 때문 => 참조 호출(call by reference)

 

H → head = NewNode;

 

 

 

 

 

 

 

 

---

03. 이중 연결 리스트

 

▪️ 단순 연결 리스트의 단점
 어떤 노드를 찾을 경우, 그 특정 노드의 후행 노드는 쉽게 찾을 수 있지만, 선행 노드를 찾으려면 복잡함

 

 

 

🔸이중 연결 리스트 노드 구조

• 양쪽 방향으로 순회할 수 있도록 링크 필드가 두개 필요함 → 시작점(head)도 두개의 링크 필요(Fhead, Lhead)
• 이중 연결 리스트의 노드 구조: 두 개의 링크 필드와 한 개의 데이터 필드

 

 

 

 

🔸이중 연결 리스트의 정의 및 생성

정의

생성

 

 

 

 

🔸이중 연결 리스트의 노드 삽입

초기모습