[C] Single Linked List 구현

모든 리스트 연산은 연산 후 바뀐 리스트의 head를 리턴. 그러면 head를 함수 내에서 굳이 더블 포인터로 받아서 변경할 필요 없음.

구조체

#include <stdio.h>
#include <stdlib.h>

struct node {
	int val;
	struct node *next;
};

struct list {
	struct node *head;
};
struct list *listp;

초기화 및 노드 생성

void list_init(struct list *l)
{
	l->head = NULL;
}

struct node *list_new_node(int val)
{
	struct node *new_node = (struct node *)malloc(sizeof(struct node));
	new_node->val = val;
	new_node->next = NULL;
	return new_node;
}

순회

링크드 리스트 노드 값이 1 -> 2 -> 3 -> 4 -> 5 -> 6 이라고 할때,

• for 문 내에서 모든 node 값 확인

  node = head;
  for (;node != NULL; node = node->next)
     printf("%d ", node->val);

  출력

  1 2 3 4 5 6

• 마지막 node로 이동

  node = head;
  for (;node->next != NULL; node = node->next)
     printf("%d ", node->val);
  printf("[%d] ", node->val);

  출력

  1 2 3 4 5 [6]

삽입 연산

struct node *list_add_front(struct node *head, struct node *newp)
{
	newp->next = head;
	return newp;
}

struct node *list_add_end(struct node *head, struct node *newp)
{
	struct node *n = head;
	if (head == NULL)
		return newp;
	for (; n->next != NULL; n = n->next)
		;
	n->next = newp;
	return head;
}

삭제 연산

struct node *list_delete_node(struct node *head, int val)
{
	struct node *n = head, *prev = NULL;
	for (;n != NULL; prev = n, n = n->next) {
		if (n->val != val)
			continue;
		if (prev == NULL)
			head = n->next;
		else
			prev->next = n->next;
		free(n);
		break;
	}
	return head;
}

Reversing 연산

//         a -> b -> c -> d -> NULL
// NULL <- a <- b <- c <- d
struct node *list_invert(struct node *head)
{
	struct node *curr = head;
	struct node *prev = NULL;
	struct node *next = NULL;
	for (;curr != NULL; prev = curr, curr = next) {
		next = curr->next;
		curr->next = prev;
	}
	return prev;
}

main()

void list_print(struct node *head)
{
	struct node *n = head;
	for (; n != NULL; n = n->next)
		printf("[%d]", n->val);
	printf("\n");
}

int main(int argc, char *argv[])
{
	listp = (struct list *)malloc(sizeof(struct list));
	list_init(listp);
	list_print(listp->head);
	listp->head = list_add_end(listp->head, list_new_node(40));
	listp->head = list_add_front(listp->head, list_new_node(30));
	listp->head = list_add_front(listp->head, list_new_node(20));
	listp->head = list_add_front(listp->head, list_new_node(10));
	listp->head = list_add_end(listp->head, list_new_node(50));
	listp->head = list_add_end(listp->head, list_new_node(60));
	list_print(listp->head);

	listp->head = list_delete_node(listp->head, 50);
	listp->head = list_delete_node(listp->head, 10);

	list_print(listp->head);

	listp->head = list_invert(listp->head);
	list_print(listp->head);

	listp->head = list_add_end(listp->head, list_new_node(90));
	list_print(listp->head);
	listp->head = list_add_end(listp->head, list_new_node(95));
	list_print(listp->head);

	listp->head = list_add_front(listp->head, list_new_node(70));
	listp->head = list_add_front(listp->head, list_new_node(80));
	list_print(listp->head);


	return 0;
}