[C로 만드는 자료구조]리스트(List) - 단순 연결 리스트(1/2)

단순연결 리스트를 만들기 전에 기본적인 사항들 몇개 짚고 가겠습니다.

노드

앞에서 보았듯이 단순연결 리스트는 앞에서 뒤로 한방향으로만 연결이 되어 있으며 제일 뒤의 노드의 Link값은 NULL이 들어갑니다. 우선 단순 연결 리스트의 노드 구조체부터 살펴보겠습니다.

typedef struct ListNode
{
    int VALUE;//값
    struct ListNode *Link;//다음 노드의 주소를 저장
}ListNode;

노드는 값을 저장하는 VALUE변수와 다음 노드를 가리키기 위한 포인터 변수로 이루어져 있습니다. 노드가 구조체이기 때문에 다음 노드를 가리키는 포인터 또한 구조체를 가리키는 포인터를 선언해 주어야합니다.

다음은 노드를 생성하는 방법입니다.

동적으로 리스트를 만드는 것이므로 노드 객체를 더 많들어서 연결해주는 것이 아니라 동적할당을 통해 노드를 동적으로 생성해서 연결을 해주는 것입니다. C언어로 구현하고 있기 때문에 malloc.h를 인클루드 시켜서 동적 메모리 생성 라이브러리 malloc 함수를 이용합니다.

ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));

다음은 데이터 필드와 링크 필드에 값 입력하는 방법입니다.

ListNode *NewNode = (ListNode *)malloc(sizeof(ListNode));
newNode->VALUE = 10;
newNode->Link = NULL;

생성후에 다음과 같이 값을 입력해 줍니다. 포인터 이기 때문에 . 연산자가 아닌 화살표(->)연산자를 이용하여 호출한뒤 대입을 해줍니다.

다음은 각 각의 두 노드를 연결하는 방법입니다.

ListNode *Node2 = (ListNode *)malloc(sizeof(ListNode));
Node2 -> VALUE = 20;
Node2 -> LINK = NULL;
newNode->Link = Node2;

2번째 노드를 생성한뒤 값을 넣어주고 첫번째 노드를 가리키고 있는 newNode 포인터를 이용하여 두번째와 첫번째를 연결해주는 소스입니다.

삽입 연산 구현 방식입니다.

week2라는 리스트에 '월', '금', '일' 이라는 자료들이 순서대로 들어가있는데 '월' 과 '금' 사이에 '수'를 넣는 연산을 그림으로 나타내면 다음과 같습니다.

1. 삽일할 새 노드를 만들 공백 노드를 메모리에서 가져와 포인터 변수 new가 가리키게 합니다.

2. new의 데이터 필드에 '수'를 저장합니다.

3. new가 들어갈 위치의 앞노드 '월'노드의 링크 필드 값을 new의 링크 필드에 저장하여 '월'의 다음이 '금'이 아니라 '수'의 다음이 '금'으로 만들어줌 

4. new의 값(new가 가리키고 있는 새 노드의 주소)을 '월' 노드의 링크 필드에 저장

위와 같이 단순 연결 리스트에서의 삽입 연산을 구현할 수 있습니다.

삭제 연산 구현 방식입니다.

week2라는 리스트에 '월' , '수' , '금' , '일' 이라는 자료들이 순서대로 들어가있는데 '월' 과 '금' 사이에 있는 '수'를 삭제하는 연산을 그림으로 나타내면 다음과 같습니다.

1. 삭제할 원소의 바로 앞 노드(선행자) 찾기

2. 삭제할 원소 '수'의 링크 필드 값을 앞 노드의 링크 필드에 저장한뒤 삭제한 원소는 동적할당 해제를 해줌

위의 방법으로 삭제 연산을 구현할 수 있습니다.

기본적인 연산과 기본적인 특징들을 알아보았습니다. 이것과 이 다음 단순 연결 리스트 구현 포스팅은 앞으로 나오는 모든 자료구조의 기반이 되게 됩니다. 다음 포스팅에서는 위에서 알아본 것들을 이용하여 여러 ADT를 구현해보겠습니다.

같이 보기

2016/01/22 - [Programming/STL] - STL(Standard Template Library) - Container - List

2015/11/07 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List)- 이중 원형 연결 리스트

2015/11/07 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List)- 단순 원형 연결 리스트

2015/11/06 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 단순 연결 리스트(2/2)

2015/11/04 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 동적 연결 리스트

2015/11/02 - [Programming/자료구조] - [C로 만드는 자료구조]리스트(List) - 배열