[자료구조] Chapter 04. List
🚨 'C언어로 쉽게 풀어쓴 자료구조' 라는 책을 활용했던 과거 수업 필기를 정리한 것입니다.
💡 Chapter 순서는 책과 같지만 교수님의 과거 수업 내용에 따라 일부 책과 다른 내용이 있습니다.
List
- data 명단으로써 배열에 저장하거나 또는 Linked List에 저장
- 모든 APT의 기본 연산
- 검색 (search)
- 수정 (modify)
- 삽입 (insert)
- 삭제 (delete)
SLL (Single-Linked List)
1. 검색 (Search)
-> Key를 찾음
// 선형 검색
p = Head
while(p != NULL)
{
if(p -> data == key) -> found!
p = p->Next
}
-> not found
※ 참고
1. 선형 검색 (linear search) -> O(n) (최선의 경우 1번, 최악의 경우 n번, 평균 n/2번)
2. 이진 검색 (binary search) -> O(lg n)
2. 삽입 (Insert)
p = (Node *) malloc(sizeof(Node));
p->data = data;
- 맨 앞에 삽입
// 순서 중요함
1. p->Next = Head;
2. Head = p;
- 중간 / 끝에 삽입 (=기존 원소가 적어도 한 개는 있음)
1. p->Next = q->Next;
2. q->Next = p;
3. 삭제 (Delete) : q 다음원소 p 삭제
if(q = Head) Head = p->Next;
else q->Next = p->Next;
free(p);
DDL(Doubly-Linked List)
1. 삽입 (Insert)
p = (Node *)malloc(sizeof(Node));
p->data = data;
- 맨 앞에 삽입
1. p->Next = Head;
2. p->Prev = NULL;
3. if(Head != NULL) Head->Prev = p;
4. Head = p;
- 중간 / 끝에 삽입 (q 다음에)
1. p->Next = q-> Next;
2. p->Prev = q;
3. if(q->Next != NULL) q->Next->Prev = p;
4. q->Next = p;
2. 삭제 (Delete)
DLL은 앞 원소가 무엇인지 알고 있음
1. if(p->Next != NULL){ // 뒤에 원소가 있을 때
p->Next->Prev = p->Prev;
}
2. if(p->Prev != NULL){
p->Prev->Next = p->Next;
}else Head = p->Next;
free(p);
원형리스트 (Circular List)
Circular DLL with Structural Head (CDLLS)
Node *Head, *p;
Head = (Node *)malloc(sizeof(Node));
1. 삽입 (Insert)
q 다음에 삽입 (q = Head 가능)
1. p->Next = q->Next;
2. p->Prev = q;
3. q->Next = p;
4. p->Next->Prev = p;
2. 삭제 (Delete)
p 삭제
1. p->Prev->next = p->Next;
2. p->Next->Prev = p->Prev;
free(p);
Author And Source
이 문제에 관하여([자료구조] Chapter 04. List), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@subinnie/자료구조-4.-List저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)