자료구조 - 연결리스트(구조체와 포인터 사용)

이는 0 이하의 값이 입력될 때까지 입력이 계속되는 간단한 예제이다.

 

 

다음과 같은 형태로 자연수를 입력으로 받고 0이하의 값이 입력되면 while 문을 빠져나와 배열을 출력한다.

 

하지만 이처럼 배열은 메모리의 특성이 정적이여서 메모리의 길이를 변경하는 것이 불가능하다.

 

위 예제를 실행한 후 0 이하의 값을 입력하지 않고 계속 입력하면 할당된 배열의 크기인 10을 넘어가는 문제가 발생한다.

 

---

 

이 문제를 해결하기 위해 정적인 배열이 아닌 동적으로 메모리를 구성하여 다음과 같은 연결리스트를 구성할 수 있다.

연결 리스트를 구현한 전체 코드

 

 

실행 결과

 

 

 

▼코드 설명

 

1. 노드 형태 구현 

여기서 data는 데이터를 담을 공간이며 struct _node *next 는 아래 그림처럼 노드의 연결을 위한 포인터이다.

 

 

 

 

 

head는 연결 리스트에서 머리를 가리키는 포인터 변수이며

tail은 연결 리스트에서 꼬리를 가리키는 포인터 변수,

cur은 연결 리스트에서 데이터 조회를 위한 포인터 변수이다.

newNode는 연결 리스트에서 새로운 노드를 생성할 때 사용하는 변수이다.

readData는 연결 리스트에서 데이터를 입력받기 위한 변수이다.

 

 

다음은 각 포인터 변수를 나타낸 그림이다.

 

---

2. 데이터 입력받는 과정

다음 코드에선 자연수를 입력받고 자연수가 1 미만이면 while 문을 탈출하여 연결 리스트에서의 노드 생성을 종료한다.

 

newNode = (Node *)malloc(sizeof(Node)); 는 하나의 노드 공간을 동적으로 할당받도록 하는 코드이다.

newNode -> data = readData; 는 만든 노드의 data 변수에 readData를 삽입한다는 의미이다. 아래 그림 표현과 같다.

 

 

readData 에 2를 입력받을 때 newNode 는 다음과 같이 된다.

 

if( head == NULL )

    head = newNode;

else

    tail -> next = newNode;

tail = newNode;

 

다음 코드에서 head==NULL 는 노드가 처음생성 되었을 때를 뜻하며

head 가 newNode 를 가리키도록 하고 tail 또한 newNode 를 가리키도록 한다.

노드가 첫 번째 이후로 생긴 노드면 tail 이 새로운 노드를 가리키도록 한다. 이 내용은 아래 그림과 같다.

 

data가 2인 노드가 처음 생성되었을 때

data 가 4인 노드가 새로 생겼을 때

---

2. 입력받은 데이터 출력과정

위 코드에서

if( head == NULL ) 은 헤더가 아무 것도 가리키고 있지 않은 경우를 뜻한다.

즉 데이터가 입력되지 않았음을 의미한다.

 

 

else 그게 아니면 cur 는 head가 가리키고 있는 첫 번째 노드를 가리키도록 하고

cur 이 가리키는 첫번 째 노드의 data 를 출력한 뒤

cur 이 가리키는 노드가 없을 때까지 노드들을 거쳐가면서 data를 출력하도록 한다. (이 과정들은 아래 그림과 같다)

 

 

---

3. 메모리 해제 과정

위 코드에서

if ( head == NULL ) 는 만약 해제할 노드가 없다면 실행을 종료한다.

else 그게 아니면 메모리를 해제하기 위한 delNode 를 선언하고 head 가 가리키는 첫 번째 노드를 가리키도록 한다.

그리고 첫 번째 노드의 "data 를 삭제합니다" 라는 문자열 출력과 함께 free로 첫 번째 노드를 반환한다.

while 문에선 delNode 를 delNextNode 를 가리키도록하고 delNextNode는 자신이 가리키고있는 노드가 가리키고 있는 노드를 가리키도록 한다. 이 후 과정은 첫 번째 노드의 메모리를 반환하는 과정과 동일하다. (이 모든 과정은 아래 그림과 같다)

 

2 삭제하는 과정(dN은 delNode, dNN은 delNextNode를 뜻함)

2 삭제 후 그 다음 노드인 4로 이동

4 삭제