<6> 단일 연결리스트

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

이걸로 계속 가겠음.🪸😎

 

 

 

🪸 리스트

 

*배열과 연산 비교

- 배열은 i번째 요소를 찾기 쉽지만, 리스트의 경우 순차적으로 탐색해야 하기 때문에 시간이 오래 걸림.

필요없다는 것은 heap mem manager가 용량이 차면 알려주기 때문

 

🪸 리스트 구현 방법

1) 배열을 이용한 구현 (순차적 표현)

*장점 : 구현이 간단하고 속도가 빠름.

*단점 : 중간에 데이터를 삽입/삭제할 때 기존 데이터를 이동해야 함.

 

😎 get_entry() 와 insert_last()의 경우 O(1) 소요

get_entry()

insert_last()

😎 pos에 있는 요소  insert() , delete()의 경우 최악: O(n) 소요

-insert()

: 마지막 항목(size-1)부터 pos까지 한 칸씩 오른쪽으로 이동하여 빈자리를 생성 후 삽입 + 사이즈 증가

 

 

-delete()

: pos에 있는 요소 반환 후 pos부터 마지막 항목(size-1)까지 왼쪽으로 한 칸씩 이동 + 사이즈 감소

 

 

---

1) 연결리스트를 이용한 구현 (연결된 표현)

: 각 항목들을 node(노드)에 분산 저장

*장점: 삽입, 삭제가 배열보다 용이함, 메모리 공간이 연속적일 필요 없음.

*단점: 구현이 어렵다, 오류 발생이 쉽다, 포인터를 위한 추가 공간 필요, 탐색이 순차적이라 O(n) 소요

 

✨노드 : 데이터 값을 저장하는 데이터 필드와, 다른 노드의 주소값을 저장(포인터)하는 링크 필드로 구성

😎 노드가 필요할 때마다 malloc()을 이용해 동적 생성!

😎 if 64bits-OS 사용하는 경우, 포인터를 이용하기 때문에 8byte가 링크 필드를 위해 필요함.

만약 4btye int 데이터를 저장하는 경우 총 12 B가 필요함. (배보다 배꼽이 크다!)

 

 

---

 

🪸 연결리스트 종류

1) 단순 연결리스트 

: 하나의 링크 필드를 이용하여 연결 + 마지막 노드의 링크 값은 NULL

-노드 정의

😎 각 노드를은 자신과 똑같은 구조체가 저장된 메모리 위치를 기억해야 하는 자기자신을 참조하는 포인터를 포함한 구조체!

 

 

-생성 : 노드의 크기만큼의 동적 메모리 할당

ListNode *p;

head = (ListNode*)malloc(sizeof(ListNode));

p->data = 20;

p->link = NULL;

 

---

✨ 단순연결리스트 연산

 

1) 삽입 연산 (p가 가리키는 노드를 맨 앞에 넣는 경우)

//p가 가리키는 노드 삽입 코드//

 

p->data = value;

p->link=head; //순서주의

head=p;

: 삽입하는 노드의 링크 필드부터 해결하는 것이 중요! 

 

 

 

2) 삽입 연산 (노드들 사이에 삽입)

 

//생략//

 

p->data = value;

p->link = pre->link;

pre->link = p;

: 이것도 삽입하는 노드의 링크부터 처리하는 걸 기억하며 돼요!

 

 

 

3) 삭제 연산(맨 앞 노드)

 

//생략//

 

removed = head;

head=removed->link;

free(removed);

: removed 변수의 중요성 : 나중에 free()를 사용하기 위해서 !!

 

✨동적 메모리 관리를 위해 더 이상 사용하지 않는 메모리를 OS에 반환해야 함. 

-> free()를 통해 heap mem의 매니저가 우리가 반납한 메모리를 다른 프로그램/세스 에게 넘겨줄 수 있다!

 

 

 

3) 삭제 연산(중간 노드)

//생략//

 

removed = pre->link;

pre->link = removed->link;

free(removed);

 

---

😎 단어들을 저장하는 연결리스트

: 결과적으로 BANANA -> KIWI -> APPLE 순으로 저장됨. (앞에 삽입)

 

 

 

😎 2개의 리스트를 합하는 함수

 

 

😎 리스트를 역순으로 만드는 연산

* r : 이미 역순으로 변경된 노드,  p : 역순으로 만들 노드

-> 3개의 임시 포인터가 필요함!

 

//생략//

 

r=q;

q=p; // r은 q, q는 p를 차례로 따라감.

p=p->link; 

q->link=r; // q의 링크 방향 변경

 

//생략//

---

🪸 연결리스트의 응용 : 다항식

: 하나의 다항식을 하나의 연결리스트로 표현

 

😎 다항식의 덧셈

계수, 지수, 링크 로 구성

 

1) p.expon == q.expon (두 식의 포인터가 가리키는 항들의 지수가 같으면)

->두 계수를 더해서 새로운 리스트에 저장.

 

2) p.expon < / > q.expon ( 두 식의 포인터가 가리키는 항들의 지수값이 차이가 있다면)

-> 더 큰 지수값을 가진 항을 새로운 리스트에 저장

 

3) 하나가 먼저 끝나게 되는 경우 나머지를 전부 새로운 리스트에 복