[열혈자료구조] 3강. 연결 리스트(Linked List) 1 - (2)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

https://cascade.tistory.com/69

[열혈자료구조] 3강. 연결 리스트(Linked List) 1 - (1)

 

앞선 포스팅에서는 배열로 정수 리스트를 구현하였고, 리스트의 구현내용을 확인하지 않고 main함수에서 이를 사용하여 ADT의 개념을 학습하였다. 본 포스팅에서는 정수가 아닌 다른 자료형을 나열하는 리스트를 구현하고 사용해 보자. 열혈자료구조 교재에 나오는 Point 구조체를 담는 리스트 예제 하나와, 직접 만든 유향선분 구조체를 담는 리스트를 다룰 것이며, 후자는 다음 포스팅에 정리하려고 한다.

https://cascade.tistory.com/71

[자작 예제] 유향선분 구조체를 저장하는 리스트

Point를 저장하는 리스트 (교재 예시)

typedef struct _point
{
	int xpos;
	int ypos;
} Point;

 

 

먼저, 열혈자료구조에 나오는 예제로, 구조체 변수의 주소 값이 저장되는 리스트를 만들어 보자. 위와 같이 정의한 Point 라는 구조체 (점의 위치를 나타낸다고 생각하자) 는 세 가지 함수를 가진다.

// 1. x좌표와 y좌표를 입력받아 ppos라는 메모리에 할당
void SetPointPos(Point * ppos, int xpos, int ypos); 

// 2. ppos에 있는 Point를 보여줌
void ShowPointPos(Point * ppos);

// 3. 두 Point를 비교함
int PointComp(Point * pos1, Point * pos2)

 

이러한 함수들이 구현된 Point.c와 헤더 파일 Point.h는 윤성우의 열혈자료구조 블로그(https://blog.naver.com/oedu/223011150597) 에서 다운로드 받을 수 있다. 이 Point 구조체 변수의 주소 값을 저장하는 리스트를 이전 포스팅에서 구현했던 ArrayList의 코드를 변경하여 구현해 보자.

 

먼저, 헤더 파일 ArrayList.h에서 정수를 받는 리스트는 아래와 같이 LData를 정의하였다.

typedef int LData;

 

이를 Point로 바꾸려면 아래와 같이 적어야 한다. 이때 Point라는 자료형을 썼으므로 "Point.h" 헤더를 ArrayList.h에 추가해야 한다.

typedef Point * LData;

 

헤더는 stdio, stdlib과 함께 "ArrayList.h"와 "Point.h"를 적어 준다. 또한, 메인 함수 안에서 아래와 같이 서넌을 해준다.

List list;
Poinr compPos;
Point * ppos;

 

---

리스트에 Point 데이터 저장

 

리스트에 Point를 저장하는 과정은 아래와 같다.

1. 메모리 동적 할당 : malloc() 함수 이용
2. 해당 공간에 x, y값을 갖는 Point 변수 할당
3. 리스트에 해당 공간의 주소 값 저장

이를 아래와 같이 구현하였다.

ppos = (Point *) malloc (sizeof(Point));
SetPointPos(ppos, 2, 1); //x = 2, y = 1
LInsert(&list, ppos);

 

이 과정을 (2, 1), (2, 2), (3, 1), (3, 2)에 대해 4번 반복하여 리스트에 4개의 데이터를 저장하자.

 

리스트에 저장된 데이터의 출력

 

현재 데이터의 수를 출력하고, ShowPointPos() 함수로 데이터를 보이자.

	printf("number of saved data: %d \n", LCount(&list));

	if(LFirst(&list, &ppos))
	{
		ShowPointPos(ppos);
		
		while(LNext(&list, &ppos))
			ShowPointPos(ppos);
	}
	printf("\n");

 

x좌표가 2인 모든 데이터 삭제

 

비교를 위해 선언한 Point 자료형 (좌표 x=2, y=0) compPos를 사용하여, compPos와 x좌표가 같은 리스트 안의 원소를 삭제하자. 이때 Point끼리 비교하는 함수 PointComp와 삭제하는 함수 LRemove를 이용한다. 또한 malloc 으로 동적할당을 했으니 꼭 free를 해 주자.

	compPos.xpos=2;
	compPos.ypos=0;

	if(LFirst(&list, &ppos))
	{
		if(PointComp(ppos, &compPos)==1)
		{
			ppos=LRemove(&list);
			free(ppos);
		}
		
		while(LNext(&list, &ppos)) 
		{
			if(PointComp(ppos, &compPos)==1)
			{
				ppos=LRemove(&list);
				free(ppos);
			}
		}
	}