[자료구조] Chapter 04. List

🚨 'C언어로 쉽게 풀어쓴 자료구조' 라는 책을 활용했던 과거 수업 필기를 정리한 것입니다.
💡 Chapter 순서는 책과 같지만 교수님의 과거 수업 내용에 따라 일부 책과 다른 내용이 있습니다.

List

• data 명단으로써 배열에 저장하거나 또는 Linked List에 저장
• 모든 APT의 기본 연산
  1. 검색 (search)
  2. 수정 (modify)
  3. 삽입 (insert)
  4. 삭제 (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. 맨 앞에 삽입
   

// 순서 중요함
1. p->Next = Head;
2. Head = p;

2. 중간 / 끝에 삽입 (=기존 원소가 적어도 한 개는 있음)
   

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. 맨 앞에 삽입
   

1. p->Next = Head;
2. p->Prev = NULL;
3. if(Head != NULL) Head->Prev = p;
4. Head = p;

2. 중간 / 끝에 삽입 (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);