연결 리스트(Linked List) 1

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 추상 자료형(Abstract Data Type)

• “구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것”

ex) 지갑 Wallet 구조체가 있을 때

type Wallet = {
  coin100Num: number;
  bill5000Num: number;

  // 돈을 꺼내는 기능
  takeOutMoney: (value: number) => { coin100: number; bill5000: number } | string;

  // 돈을 넣는 기능
  putMoney: (coin100: number, bill5000: number) => void;
};

• 추상 자료형도 자료형이기에 ‘기능’ 혹은 ‘연산’과 관련된 내용을 명시할 수 있음

 

2. 배열을 이용한 리스트의 구현

2.1. 리스트의 이해

• 순차 리스트: 배열을 기반으로 구현된 리스트
• 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트
• 리스트 자료구조는 데이터를 나란히 저장하고 중복된 데이터의 저장을 막지 않음
• 리스트 자료구조의 ADT

void ListInit(List *plist); 
- 초기화할 리스트의 주소 값을 인자로 전달 
- 리스트 생성 후 제일 먼저 호출되어야 하는 함수 

void LInsert(List *plist, LData data); 
- 리스트에 데이터를 저장함. 매개변수 data에 전달된 값을 저장 

int LFirst(List *plist, LData *pdata); 
- 첫번째 데이터가 pdata가 가르키는 메모리에 저장된다 
- 데이터의 참조를 위한 초기화가 진행된다. 
- 참조 성공 시 TRUE, 실패 시 FALSE 반환 

int LNext(List *plist, LData *pdata); 
- 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다. 
- 순차적인 참조를 위해서 반복 호출이 가능하다. 
- 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 함 
- 참조 성공 시 TRUE, 실패 시 FALSE 반환 

LData LRemove(List *plist, LData target); 
- LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제 
- 삭제된 데이터는 반환함 
- 마지막 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않음 

int LCount(List *plist); 
- 리스트에 저장된 데이터 수를 반환​

 

2.2. 리스트 구현 방법

1. 헤더파일의 정의
   • 구조체 ArrayList는 데이터의 저장공간을 배열로 선언했고 저장된 데이터의 수를 기록하기 위한 멤버도 있음
   • LFirst, LNext, LRmove 함수를 위한 멤버도 존재함.
   • 리스트에 다양한 종류의 데이터를 저장할 수 있도록 typedef 선언도 해줌
     • typedef ArrayList List;
2. 삽입과 조회
   • 헤더파일에 선언된 함수들을 정의함.
     • 배열초기화 및 데이터 저장

     void ListInit(List * plist); // 초기화
     void LInsert(List * plist, LData data);  // 데이터 저장
     
     
     void ListInit(List * plist)
     {
     	(plist -> numOfData) = 0; // 리스트에 저장된 데이터 수 = 0
     	(plist -> curPosition) = -1; // 현재 아무 위치도 가리키지 않음
     }
     
     void LInsert(List * plist, LData data)
     {
     	if(plist ->numOfData >= LIST_LEN) // 더 이상 저장할 공간이 없다면
     	{
     		puts("저장이 불가능합니다.");
     		return;
     	}
     	
     	plist->arr[plist->numOfData] = data; // 데이터 저장
     	(plist -> numOfData)++; // 저장된 데이터 수 증가
     }

     • 조회

     int LFirst(List * plist, LData *pdata); // 첫번째 조회
     int LNext(List * plist , LData *pdata); // 두번째 이후 조회
     
     int LFirst(List * plist, LData *pdata)
     {
     	if(plist->numOfData == 0) // 저장된 데이터가 하나도 없으면
     		return FALSE;
     		
     	(plist->curPosition) = 0; // 참조위치 초기화 (첫번째 위치를 의미)
     	*pdata = plist->arr[0]  // pdata가 가리키는 공간에 데이터 저장
     }
     
     int LNext(List * plist, LData *pdata)
     {
     	if(plist->curPosition >= (plist->numOfData)-1) // 더 이상 참조할 데이터가 없다면
     		return FALSE;
     	
     	(plist->curPosition)++;
     	*pdata = plist->arr[plist->curPosition];
     	return TRUE;
     }

3. 삭제 + count
   • LFirst 함수나 LNext 함수의 호출을 통해서 바로 직전에 참조가 이뤄진 데이터를 삭제하는 것
   • LRemove 함수가 호출되면 리스트의 멤버 curPositrion을 확인해서 조회가 이뤄진 데이터의 위치를 확인한 후, 그 데이터를 삭제
   • 그리고 앞에서부터 데이터를 채우는 것이 원칙이기 때문에 중간 데이터가 삭제되면 뒤에 저장된 데이터들은 한칸씩 앞으로 이동시켜 그 빈 공간을 채워야 함

   LData LRemove(List * plist); // 최근 조회가 이루어진 데이터를 삭제
   
   LData LRemove(List *plist)
   {
   	int rpos = plist->curPosition; // 삭제할 데이터의 인덱스 값 참조
   	int num = plist->numOfData;
   	int i;
   	LData rdata = plist->arr[rpos]; // 삭제할 데이터를 임시로 저장
   	
   	// 삭제를 위한 데이터의 이동을 진행하는 반복문
   	for(i=rpos; i<num; i++)
   		plist->arr[i] = plist-> arr[i+1];
   	
   	(plist->numOfData)--;  // 데이터의 수 감소
   	(plist->curPosition)--;  // 참조위치를 하나 되돌린다. (데이터 하나가 없어져 다 앞으로 이동해서)
   	 return rdata;  // 삭제된 데이터의 반환
   }
   
   // 리스트에 저장된 데이터 수 반환
   int LCount(List * plist)
   {
   	return plist->numOfData;
   }
   

 

2.3. 리스트에 구조체 변수 저장

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

// Point 변수의 xpos, ypos 값 설정
void SetPointPos(Point *ppos, int xpos, int ypos)
{
	ppos->xpos = xpos;
	ppos->ypos = ypos;
}

// Point 변수의 xpos, ypos 정보 출력
void ShowPointPos(Point *ppos)
{
	printf("[%d, %d] \\n", ppos->xpos, ppos->ypos);
}

// 두 Point 변수의 비교
int PointComp(Point *pos1, Point *pos2)
{
	if(pos1->xpos == pos2->xpos && pos1->ypos == pos2->ypos)
		return 0;
	else if(pos1->xpos == pos2->xpos)
		return 1;
	else if(pos1->ypos == pos2->ypos)
		return 2;
	else
		return -1;
}

 

2.4. 배열의 장점과 단점

• 배열 기반 리스트의 단점
  • 배열의 길이가 초기에 결정되어야 하며 변경이 불가능
  • 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번하게 일어남
• 배열 기반 리스트의 장점
  • 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능

 

 

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)