개요
임의의 디렉토리 내에 존재하는 파일의 목록을 소프트웨어가 필요로 할때 배열로 불러오기엔 한계가 있다. 이땐 배열처럼 데이터 집합을 보관하는 기능을 가지면서도 한편으로는 배열과 달리 유연하게 크기를 바꿀 수 있는 자료구조인 링크드 리스트를 이용하면 된다.
cf) 리스트는 스택, 큐, 트리와 같은 자료구조를 이해할 수 있는 기반이 되는 점에서도 의미를 가진다. 따라서 리스트를 통해 자료구조를 다루기 위해 필요한 메모리 처리 기법에 익숙해지자.
링크드 리스트
node는 한국어로 마디라는 뜻이며, 링크드 리스트는 '노드를 연결해서 만드는 리스트'라고 해서 붙여진 이름이다.
링크드 리스트의 구조는 다음과 같이 데이터를 보관하는 필드(1번)와, 다음 노드와의 연결 고리 역할을 하는 포인터(2번)로 이루어진다.
리스트의 첫 번째 노드를 헤드라 하고, 마지막 노드를 테일이라고 한다.
링크드 리스트의 장점으로는 다뤄야하는 데이터 집합의 크기를 미리 알지 못하더라도, 데이터가 늘어날 때마다 노드를 만들어 테일에 붙이면 된다.
특징
자료가 연결되어있기 때문에 새로운 자료를 앞쪽에 추가/삭제할때 굉장히 유용하게 사용할 수 있다. 하지만 무조건 순회하며 찾아가는 과정이 필요하기 때문에 특정한 노드를 찾기가 까다롭다.
링크드 리스트의 주요 연산
노드 생성/소멸
C언어로 작성된 프로그램은 다음과 같은 세 가지 종류의 메모리 영역을 가진다.
정적메모리 : 전역 변수나 정적 변수 등이 저장되고, 프로그램이 실행하면서 프로그램에서 사용될 전역 변수/정적 변수를 메모리에 할당한 후 프로그램이 종료될 때 해체하는 영역
자동메모리 : 스택구조로 되어있으며, 지역 변수가 저장된다.
코드블럭({})안에서 선언된 변수들은 선언 당시에 자동 메모리에 저장되었다가 코드 블록의 끝에서 모두 제거된다.
int Plus( int a, int b) /*a와 b도 자동 메모리에 저장된다.*/
{
int c = a+b; /*c도 물론 자동 메모리에 저장된다.*/
return c;
} /*a,b,c 모두 자동 메모리에서 제거된다. */자유 저장소 : 프로그래머가 직접 메모리를 관리하는 메모리 영역이다. 여기서 '자유'란, 자동 메모리 영역에서 코드 블록이라는 한계로부터의 해방을 의미한다.
노드의 생성 : 자동메모리 vs 자유저장소
(1) 자동 메모리
Node* SLL_CreateNode( int NewData )
{
Node NewNode; /*자동 메모리에 새로운 노드 생성*/
NewNode.Data = NewData;
NewNode.NextNode = NULL;
return &NewNode; /* NewNode가 생성된 메모리의 주소를 반환*/
} /*함수가 종료되면서 NewNode는 자동 메모리에서 제거된다.*/
...
Node* MyNode = SLL_CreateNode(117); /*MyNode는 할당되지 않은 메모리를 가리킨다.*/이 경우, SLL_ CreateNode() 함수 안에서 생성된 NewNode는 함수가 종료하면서 자동 메모리에서 제거된다.
하지만 SLL_CreateNode() 함수는 NewNode가 존재했던 메모리의 주소를 반환한다. 한마디로 엉뚱한 메모리를 가리키고, 프로그램은 죽어버리거나 엉뚱한걸 가르키게 되는 일이 생긴다.
(2) 자유 저장소
자유 저장소에 메모리를 할당하려면 malloc()함수가 필요하다.
- malloc() 함수의 반환형인 void*는 어떤 형이라도 가리킬 수 있다.
이는 곧 malloc() 함수가 할당한 자유 저장소의 메모리 주소를 어떤 형의 포인터라도 가리킬 수 있다는 것을 의미한다.
- 노드 생성
Node* NewNode = (Node*)malloc(sizeof(Node));malloc() 함수는 sizeof 연산자가 측정한 노드의 크기만큼 자유 저장소에 할당한 후, NewNode에 그 메모리 주소를 저장한다.
/* 노드 생성 */
Node* SLL_CreateNode (ElementType NewData)
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = NewData; /* 데이터를 저장한다.*/
NewNode->NextNode = NULL; /* 다음 노드에 대한 포인터는 NULL로 초기화한다*/
return NewNode; /* 노드의 주소를 반환한다*/
}위의 함수는 malloc() 함수를 사용하여 노드를 자유 저장소에 생성하는 예제이다.
- 노드 소멸
노드의 소멸은 free() 함수에게 노드가 있는 주소를 알려주기만 하면 모두 free()함수가 처리한다.
void free (void *memblock);/*노드 소멸*/
void SLL_DestroyNode (Node* Node)
{
free (Node);
}SLL_은 뭘까?
Singly Linked List의 약자. 링크드 리스트는 한쪽 방향으로만 엮여 있기 때문에 Singly라는 수식어를 붙여 구분을 확실히 한 것이다.
노드 추가
링크드 리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결하는 것을 의미한다.
SLL_CreateNode() 함수를 이용하여 자유 저장소에 노드를 생성한 다음, 새로 생성한 노드의 주소를 테일의 NextNode 포인터에 대입하면 된다.
노드 추가 연산을 수행하는 SLL_AppendNode() 함수는 다음과 같다.
/*노드 추가*/
void SLL_AppendNode (Node** Head, Node* NewNode)
{
/* 헤드 노드가 NULL이라면 새로운 노드가 Head */
if ( (*Head) === NULL)
{
*Head = NewNode;
}
else
{
/* 테일을 찾아 NewNode를 연결한다. */
Node* Tail = (*Head);
while ( Tail->NextNode !=NULL )
{
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
}
}
Node* List = NULL;
Node* NewNode = NULL;
NewNode = SLL_CreateNode( 117 ); /*자유 저장소에 노드 생성*/
SLL_AppendNode( &List, NewNode); /*생성한 노드를 List에 추가*/
NewNode = SLL_CreateNode( 119 ); /*자유 저장소에 또 다른 노드 생성*/
SLL_AppendNode( &List, NewNode); /*생성한 노드를 List에 추가*/노드 탐색
탐색 연산은 링크드 리스트가 갖고 있는 약점 중 하나이다. 배열이 인덱스를 이용하여 즉시 원하는 요소를 취할 수 있게 하는데 반해, 링크드 리스트는 헤드부터 시작해서 다음 노드에 대한 포인터를 징검다리 삼아 차근차근 노드의 수를 세어나가야만 원하는 요소에 접근할 수 있다.
링크드 리스트 내에서 임의의 위치에 있는 노드를 찾아 반환하는 SLL_GetNodeAt() 함수는 다음과 같이 구현할 수 있다.
/*노드 탐색*/
Node* SLL_GetNodeAt (Node* Head, int Location)
{
Node* Current = Head;
while ( Current !=NULL && (--Location) >=0)
{
Current = Current -> NextNode;
}
return Current;
}Node* List = NULL;
Node* MyNode = NULL;
SLL_AppendNOde (&List, SLL_CreateNode( 117 ) ); /*노드를 생성하여 List에 추가*/
SLL_AppendNOde (&List, SLL_CreateNode( 119 ) ); /*노드를 생성하여 List에 추가*/
MyNode = SLL_GetNodeAt(List, 1); /* 두 번째 노드의 주소를 NewNode에 저장 * /
printf ( "%d\n", MyNode-›Data ) ; /* 119를 출력 */코드가 말끔하지만 내부 구현은 엄청난 비효율성을 품고있다. 이러한 노드 탐색의 비효율성은 링크드 리스트의 문제점 중 하나이다.
노드 삭제
삭제하고자 하는 노드를 찾은 후, 해당 노드의 다음 노드를 이전 노드의 NextNode 포인터에서 제거하면 된다.
void SLL_RemoveNode (Node** Head, Node* Remove)
{
if ( *Head == Remove)
{
*Head = Remove->NextNode;
}
else
{
Node* Current = *Head;
while ( Current != NULL && Current -> NextNode != Remove)
{
Current = Current->NextNode;
}
if ( Current != NULL)
Current->NextNode = Remove->NextNode;
}
}
삭제한 노드는 쓸 곳이 없다면 그 자리에서 바로 파괴하는게 좋다.
Node* List = NULL;
Node* MyNode = NULL;
SLL_AppendNode (&List, SLL_CreateNode( 117 ) ); /*노드를 생성하여 List에 추가*/
SLL_AppendNode (&List, SLL_CreateNode( 119 ) ); /*노드를 생성하여 List에 추가*/
SLL_AppendNode (&List, SLL_CreateNode( 212 ) ); /*노드를 생성하여 List에 추가*/
MyNode = SLL_GetNodeAt ( List, 1 ); /* 두 번째 노드의 주소를 NewNode에 저장*/
printf( "%d\n", MyNode->Data ); /* 119를 출력*/
SLL_RemoveNode( &List, MyNode ); /*두 번째 노드 제거*/
SLL_DestroyNode( MyNode ); /* 링크드 리스트에서 제거한 노드를 메모리에서 완전히 소멸*/노드 삽입
노드와 노드 사이에 새로운 노드르 끼워넣는 연산이다.
/*노드 삽입 */
void SLL_InsertAfter (Node* Current, Node* NewNode)
{
NewNode->NextNode = Current->NextNode;
Current->NextNode = NewNode;
}포인터 : 프로그래밍 언어에서 다른 변수, 혹은 그 변수의 메모리 공간주소를 가르키는 변수를 말한다.
포인터가 가리키는 값을 가져오는 것을 역참조라고 한다.
뇌를 자극하는 알고리즘
https://overcome-the-limits.tistory.com/16
https://webruden.tistory.com/1052
