Chapter 4-3 : List (Operation)

Chain 형태

typedef struct list_node *list_pointer;
typedef struct list_node{
       char data;
       list_pointer link;
};

Invert (연결 리스트 거꾸로)

list_pointer invert(list_pointer lead) {
	list_pointer middle, trail;
	middle = NULL;
	while (lead) {
		trail = middle;
		middle = lead;
		lead = lead->link;
		middle->link = trail;
	}
	return middle;
}

middle이 맨 앞으로 가고 lead가 NULL이 되면 함수가 종료됩니다.

마지막 모습

---

Comcatenate (연결 리스트 연결)

 

list_pointer concatenate(list_pointer ptr1, list_pointer ptr2) {
	list_pointer temp;
	if (IS_EMPTY(ptr1)) return ptr2;
	if (IS_EMPTY(ptr2)) return ptr1;

	for (temp = ptr1; temp->link; temp = temp->link);
	temp->link = ptr2;
}

---

Circular 형태

Insert (연결리스트 맨앞에 삽입)

 

오른쪽 그림과 같은 형태로

만드는 것입니다.

 

 

void insert_front(list_pointer* last, list_pointer node) {
	if (IS_EMPTY(*last)) {
		*last = node;
		node->link = node;
	}
	else node->link = (*last)->link;
	(*last)->link = node;
}

---

Length (연결리스트 node 개수 세기)

 

int length(list_pointer last) {
	list_pointer temp;
	int count = 0;
	if (last) {
		temp = last;
		do {
			count++;
			temp = temp->link;
		} while (temp != last);
	}
	return count;
}