<7> 원형 연결리스트, 이중 연결리스트

이 글은 시험이 15시간정도 남은 사람이 내용 정리를 위해 적는 글입니다.
*[C언어로 쉽게 풀어쓴 자료구조]  책과 숙영리 교수님의 강의를 참고하여 작성하였음을 밝힙니다.

아 또 바꾸고 싶음! 🫥👑 요걸로 하겠다

 

 

👑 원형 연결 리스트

: 마지막 노드의 링크가 첫번쨰 노드를 가리키는 리스트 

* 장점: 임의 노드에서 다른 모든 노드로 접근이 가능, 리스트의 맨 앞/뒤의 노드 삽입/삭제 용이

 

 

🫥헤드 포인터가 마지막 노드를 가리키게 구성하면 ! 리스트의 처음/마지막에 노드를 삽입하는 연산이 O(1)

*이름은 head지만 첫번째 노드를 가리키지 않음에 주의!

 

 

🫥연산

 

1) 처음에 삽입

 

 

//생략//

 

node->link = head->link;

head->link = node;

 

 

2) 끝에 삽입

이 그림은 삽입이 완료된 후

//생략//

 

node->link = head->link;

head->link = node;

head = node;

: head의 위치만 바꿔주면 그게 마지막노드임!

 

 

👑 원형 연결 리스트 응용

 

1) OS

: 모든 응용프로그램이 완료될 때까지 원형 연결리스트 순회

 

2) 원형큐

*head를REAR로, head->link를 FRONT로 사용

*insert_last(head,data)로 enqueue() 구현.

*delete_first(head)로 dequeue() 구현.

 

 

---

 

! 단순 연결리스트의 문제점 : 선행노드를 찾기 힘들다 !

 

👑 이중 연결리스트 

: 하나의 노드가 선행 노드와 후속 노드에 대한 두 가지 링크(llink와 rlink)를 가지는 리스트

*단점 : 공간 차지 ↑, 코드가 복잡

🫥 헤드노드

: 데이터를 가지지 않고 , 단지 삽입/삭제 코드를 간단하게 할 목적으로 만들어진 노드 ( != 헤드포인터)

*공백 상태에서는 헤드노드만 존재함.

 

 

🫥연산

 

1) 삽입 연산 ( 새로운 노드를 before 노드의 오른쪽에 삽입 )

//생략//

 

new_node->llink = before;

new_node->rlink = before->rlink;

before->rlink->llink = new_node;

before->rlink = new_node;

 

: 대박 이거 적는데 순서 바꿔저글 뻔  햇서요.. 휴우! 답 적어보고 검증의 과정을 거치자! 

 

 

 

2) 삭제 연산

 

//생략//

 

removed->llink->rlink = removed->rlink;

removed->rlink->link = removed->llink->rlink;

free(removed);

 

 

연습!

정답은 

1) head

2) before

3) before->rlink

4) before->rlink->llink

5) before->rlink

 

 

---

 

👑 연결 리스트로 구현한 스택

* 크기 제한이 없다는 장점이 있다!

 

 

🫥연산

 

 

-노드 선언 

* 배열로 스택을 구현할 때는 top 변수를 정수로 선언했는데 지금은 포인터로 선언중!

 

 

- 삽입 연산( = 단순 연결리스트에서 맨 앞에 데이터를 삽입하는 것 )

temp->link = s->top;

s->top = temp;

스택할 때는 s->가 붙는군....

 

 

-삭제연산

s->top = s->top->link;

free(temp);

 

 

---

 

👑 연결 리스트로 구현한 큐

: 단순 연결리스트에 포인터 2개를 추가한 것과 같음.

 

 

🫥연산

 

큐는? rear(전단)에서만 삽입된다......

 

1) 삽입 연산

q->rear->link = temp;

q->rear = temp;

큐할 때는 q->가 붙는군....

 

 

2) 삭제 연산

data= temp-> data; //data 꺼내기

q->front = q->front->link;

free(temp);

오 요거 좀 특이함! 근데 그림 보면 이해할 수 있서..!!!

 

만약에 요기서 제거하려는 노드가 처음이자 마지막 노드라면

data= temp-> data; //data 꺼내기

q->front = q->front->link;

q->rear = NULL; 

free(temp);