(C/C++) 단방향 연결리스트 [Single Linked List] (삽입, 삭제)

싱글링크드 리스트에 대하여 알아보자.

 

* 관련글 (양방향/이중 연결리스트)

[REAL Code] - (C/C++) 양방향/이중 연결리스트 구현하기 [Double Linked List] (삽입, 삭제, 탐색)

(C/C++) 양방향/이중 연결리스트 구현하기 [Double Linked List] (삽입, 삭제, 탐색)

 

학교다닐때는 링크드리스트가 얼마나 헷갈리던지 ~

자료구조 과제를 할때마다 고생에 고생을 했던 기억이 난다. 물론 대부분 검색?으로 인한 고생이었다.

당시 샘플 코드를 검색하면 malloc(), free() 와 같은 동적할당 코드가 많아서 더 눈에 들어오지 않았던것 같다.

 

혹여나 공부하시는 분들을 위해, 나처럼 좌절하지 않도록 ㅎ

정리해보자.

 

싱글리스트 같은 경우는 삽입과, 삭제가 전부라해도 과언이 아니다.

세세하게 나누면 탐색까지도 분류할 수 있겠지만 삭제하는 과정에서 탐색은 포함된다.

 

1) 초기화

싱글리스트 초기화

Tail이라는 노드를 하나 생성하여 Null 포인트를 가리키도록 한다.

구조체 크기는 임의로 크게 1000으로 잡았고, 싱글리스트다 보니 포인트 하나를 포함하여 노드를 선언했다.

노드를 초기화할때 myalloc()함수를 아래와 같이 쓰는데 동적 자료구조를 활용하여 알고리즘을

구현 할때 쓰는 나만의 유용한? 방법이다. 

struct NODE {
	int data;
	NODE* prev;
} a[1000];

int arr_idx = 0;
NODE* tail;
NODE* myalloc()
{
	return &a[arr_idx++];
}
void Init_list()
{
	arr_idx = 0;
	tail = myalloc();
}

 

2) 노드 삽입

삽입을 위해선 p라는 임의의 노드를 생성하고 

Tail의 포인터를 아래 순서대로 복사해주면 된다.

순서1

순서2

 

void Add_list(int data, NODE* ta)
{
	NODE* p = myalloc();
	p->data = data;
	p->prev = ta->prev;      // 순서 1
	ta->prev = p;            // 순서 2
}

 

3) 노드 삭제

노드 삭제는 리스트를 Tail에서부터 순회를 하면서 삭제를 할 수 있다.

아래의 pp라는 노드가 삭제되면 기존 prev가 남게 되지만 Tail이 이미 다음 노드를 가리키기 때문에

후속처리를 따로 해주지 않아도 무방하다.

노드 삭제

 

void Del_list(int data, NODE* ta)
{
	for (NODE* pp = ta->prev; pp != NULL; pp = pp->prev)     // 순회
	{
		if (pp->data == data)
		{
			ta->prev = pp->prev;
		}
		ta = pp;			
	}
	
}

노드삭제 코드에서

'순회' 부분만 활용하면 노드 탐색 구현도 가능하다.

 

전체 소스코드 공유~!

#include <stdio.h>

struct NODE {
	int data;
	NODE* prev;
} a[1000];

int arr_idx = 0;
NODE* tail;
NODE* myalloc()
{
	return &a[arr_idx++];
}
void Init_list()
{
	arr_idx = 0;
	tail = myalloc();
}



void Add_list(int data, NODE* ta)
{
	NODE* p = myalloc();
	p->data = data;
	p->prev = ta->prev;  
	ta->prev = p;
}

void Del_list(int data, NODE* ta)
{
	for (NODE* pp = ta->prev; pp != NULL; pp = pp->prev)     // 순회
	{
		if (pp->data == data)
		{
			ta->prev = pp->prev;
		}
		ta = pp;			
	}
	
}


int main(void)
{
	Init_list();

	for (int i = 1; i <= 10; i++)
	{
		Add_list(i * 10, tail);
	}
	Del_list(100, tail);
	Del_list(20, tail);
	
	for (NODE* pp = tail->prev; pp != NULL; pp = pp->prev)
	{
		printf("%d ", pp->data);
	}

	return 0;
}

 그리고 실행결과

 

 

감사합니다 ^^