6. 자료구조 - 연결 리스트 : 코딩

위 구조체를 통해 연결 리스트를 구현해 보자.

 

첫 연결 리스트를 어떻게 나타낼 수 있을까??

위 그림처럼 첫 리스트는 비어있다. 비어있는 무언가를 나타낼 때는 최소한 무언가가 필요하다.

위 그림의 빈 박스는 node를 가리키는 pointer 라고 생각해보자.

 

그렇다면 아직 비어있는 연결 리스트를 어떻게 구현할 수 있을까??

위와 같이 구현하면 된다.

 

node * 를 만들고 이를 list 라고 부른 다음 NULL 로 지정한다.

1, 2, 3 모두 없고 들어있는 숫자가 아직 없다면 적어도 리스트가 없다는 것을 알려주는 변수가 있어야 한다. 그리고 값이 없을 때 이를 표현하는 방법은 0을 저장해서 NULL 값을 가지도록 한다.

위 코드가 list 상자가 비어있는 이미지를 코드로 구현한 것이다. 이는 리스트가 비어있기 때문에 숫자가 없는 것이다. 

하지만, NULL 로 초기화 했기 때문에 어떤 메모리 덩어리를 가리키는 화살표가 아직 없다는 것이다.

 

이제 이 리스트에 숫자를 넣어보자.

위 그림처럼 숫자 2를 추가해보자. 이떄 2만 넣기 위한 공간을 할당하는 것이 아닌 2와 pointer 를 넣을 공간을 할당해야 한다. 즉, node 를 위한 공간을 할당해야 하는 것이다.

 

위 이미지를 어떻게 구현해야 할까??

위와 같이 node *n 에 node 크기의 메모리를 할당해주면 된다.

즉, 임시 변수 n 에 저장한 것이다. 엄밀히 말하면 node *n 에 malloc 이 반환한 주소가 들어가게 된다.

 

node 를 할당받았으니 이제 숫자 2와 pointer 를 넣어줘야 한다. 어떻게 해야할까??

위 이미지는 2를 넣어주기 위한 코드이다.

2번째 줄의 의미는 node 의 number 를 2로 설정한 것이다.

*n 은 가리키는 곳으로 간다는 의미이다. (   ) 은 연산의 순서를 위해 넣은 것이다. 컴파일러는 이를 인식해서 (    ) 안을 먼저 처리한다.

따라서, 가리키는 node 로 접근하고 .number 를 통해 number 필드에 접근한다. 그리고 필드에 2를 저장한 것이다.

 

정리하면, n에 있는 주소에 해당하는 메모리 덩어리(node)에 가서 number 필드에 접근하여 2로 만들어주는 코드이다.

 

C 에서는 이를 더 간단하고 예쁘게 표현할 수 있는 문법이 있다.

"->" 화살표 기호를 활용한다. 이는 (*n).number 와 동일한 의미를 가진다.

 

이렇게 node 의 number 에 2를 저장했으니 그 다음은 next 필드에 다음 node 의 주소를 넣어야한다.

하지만, 아직 다음 node 가 없기 때문에 NULL 을 넣는다. 이를 위해 n->next = NULL; 을 입력한다.

 

이때 malloc 을 사용했으니 검사를 해줘야한다.

malloc 이 반환한 값을 확인하기 위해 if 문을 작성한다. 

즉, n이 NULL 이 아닌지 확인되기 전까지는 n을 건드리거나 화살표를 사용해서는 안된다.

 

앞선 코드를 그림으로 표현하면 다음과 같다.

그림을 보면 알 수 있듯이 연결되어 있지 않기 때문에 아직 연결리스트가 아니다.

어떤 포인터에서 어떤 구조체로 향하도록하는 것과 같은 명령을 해줘야 한다.

 

즉, 궁극적으로는 다음과 같은 화살표를 나타내줘야 한다.

위 그림을 어떻게 코드로 구현해야 할까??

 

다음과 같이 해주면 된다.

매우 간단하다. list 가 n 과 같은 것을 가리키도록 한 것이다.

list 는 node 를 가리키는 포인터 변수였다. 하지만, 이전엔 NULL 을 가지고 있었다.

n 은 새로운 node 를 가지고 잇는 임시 변수였다.

 

따라서, list = n; 을 통해 list 는 더 이상 NULL 이 아니고, 방금 할당한 메모리 덩어리의 주소와 같은 값을 가져야 연결리스트가 완성된다. 

위 코드를 통해 이제 list 가 화살표를 가지고 2 node 를 가리키게 되었다.

 

그렇다면 이제 리스트에 숫자 4를 추가하고 싶다고 해보자. 어떻게 해야할까?

4는 위 그림과 같이 새로운 node 안에 들어있어야 한다.

 

따라서,

다음과 같이 4를 넣기 위한 새로운 node 를 할당하면 되는 것이다.

 

그리고 리스트로 연결하기 위해서 화살표를 추가해야 한다. 어떻게 해야할까??

list 가 4가 저장된 node 를 가리키도록 하면 안된다. 그렇게 되면 2가 저장된 node 가 버려지게 된다.

따라서 그림과 같이 2의 포인터가 4를 가리키도록 해야한다. 

이런 빵부스러기 같은 것들을 잘 따라가보기 위해 임시로 포인터 하나를 선언하고 tmp 라고 해보자.

이 tmp 포인터 변수를 list 가 가리키고 있는 것과 같은 곳을 가리키게 한다. 

그리고 이 구조체의 next 가 NULL 값인지 체크한다. 

만일 NULL 이라면 리스트의 끝을 찾은 것이다. next 가 NULL 인것을 알면 그 포인터에 새로 할당한 node 의 주소를 넣어줘서 next 가 새로 할당한 node를 가리키게 하면 되는 것이다.

 

이것을 코드로 구현해보자.

임시 변수 tmp 가 list 와 같은 곳을 가리키도록 하고,

그 다음

while 문을 통해 tmp 가 가리키는 곳의 next 필드가 NULL 이 아니면 {    } 안의 코드를 실행하는 것이다.

 

{    } 안의 코드는 다음과 같이 해줘야한다.

위 코드의 의미를 생각해보면,

내가 무엇을 가리키고 있든 next 필드를 가리키라는 것이다. NULL 이 아니라면 계속해서 자신을 업데이트해서 그 자신이 가리키고 있는 것을 가리키도록 하는 것이다.

즉, node *tmp = list; 를 통해 처음에는 2를 가리키고 있다가 2 node 의 next 가 NULL 이 아니면 그 next 가 가리키는 node 로 가는 식으로 계속해서 화살표를 따라 움직여서 next 필드가 NULL 값인 노드를 찾을 때까지 반복한다는 의미이다.

 

이렇게 계속 반복하다가 node 의 next 가 NULL 인 node 를 찾게되면

반복문을 빠져나오게 되고 포인터를 하나 더 만들어서 다음 노드를 가리키도록 해야한다.

즉, tmp -> next = n; 을 통해 새로 할당된 node 를 가리키도록 하면 되는 것이다. 2 node 의 next 가 NULL 인것이 확인되었고 그 next 에 새로 할당한 4 node 의 주소인 n 을 넣는 것이다.

 

따라서, 다음 그림과 같이

4 까지 연결된 연결 리스트가 완성된다.

 

또 다시 5를 추가하고 싶다면,

5를 넣을 node 를 만들고

 

이를 기존 연결리스트에 연결하기 위해

다시 임시 변수를 만들어서 화살표를 따라가며 NULL 을 확인하고 next 가 NULL 이면 tmp->next = n; 을 통해 5 node 를 연결시키면 된다.

 

이렇게 하여 다음 그림이 완성된다.

2, 4, 5가 연결된 연결리스트가 완성되었다.

 

그런데 만약 아래 그림과 같이 숫자 1인 node 를 추가하려면 어떻게 해야할까?? ( 이때 숫자를 정렬해야 한다는 목표가 있다.)

즉, 이미 만들어진 연결리스트에 사이 값을 넣으면서 정렬되도록 하기 위해서는 어떤 점을 고려해야할까??

 

우선,

1 node 를 만들어야 한다. 따라서, 새로운 node를 할당하는 코드로 1 node 를 만든다.

 

그런 다음, 사실 우리는 아래 그림과 같이

list 의 시작 부분에 1 을 넣어야 한다고 생각할 수 있다.

하지만, 이 방법은 코드에서 잘못되지 않았지만 방식이 잘못되었다.

 

만약 위와 같이 list 가 1 을 가리키게 하면

기존의 2, 4, 5 가 버려지게 된다. 

즉, 더 이상 아무것도 2를 가리키지 않으면 2가 4를 가리키고 4가 5를 가리킨다 하더라도 2가 버려지면서 4, 5도 같이 버려진다.

이것이 바로 메모리 누수이다.

valgrind 를 사용할 때 메모리가 누수되서 경로를 띄운다면 아마 메모리를 free 하지 않았기 때문일 것이다. 혹은 더 심한 경우 우리가 사용하던 메모리를 완전히 잃어버린 것일 수도 있다. 

위 그림을 보면 버려진 메모리에 다시는 접근할 수 없게 된다. 컴퓨터에 요청할 수 있지만 다시 되돌려 받을 수 없다. 버려진 메모리들이 어디있는지 기억하고 있는 변수가 없기 때문이다.

 

그렇다면 어떻게 해야할까??

위 그림과 같이 1도 2를 가리키도록 하는 것이다. 즉, 중복시키는 것이다.

이렇게 하면 리스트의 시작점이 어디인지 충돌이 생긴다.

하지만, 1이 2를 가리키고 있으니

 

아래 그림과 같이

list 가 1을 가리키도록 하면 정상적인 리스트가 완성된다.

 

이를 코드로 표현하면

위 그림과 같다. 위 두줄을 통해 방금의 과정을 구현한 것이다.

1을 가지고 있는 방금 할당한 새로운 node 의 next 필드를 업데이트할 때 list 가 가리키고 있는 곳을 가리키도록 만들고( n->next = list; )

list 는 n 그 자체를 가리키도록 하면 된다. ( list = n; )

 

이제 3을 리스트에 정렬되게 추가하고 싶다고 하자.

우선 3 을 위한 node 에 사용하기 위해 메모리를 할당받고, 

 

3이 4를 가리키도록 하는 것이다.

 

그 다음 2가 3을 가리키도록 하면 된다.

그러나 이를 위해선 몇 개의 추가적인 단계가 필요하다. 

아마도 loop 를 이용하여 원래 존재하던 리스트를 탐색해야하고 또한, 부등호를 사용해서 중간에 삽입할 적절한 위치를 찾아내야 한다.

따라서, 이 일을 하기 위해 포인터를 만들어야 하고 반복문과 대소 비교와 포인터를 업데이트하는 과정이 필요하게 된다.

그래서, 일반적으로는 리스트 맨 뒤에 새로운 값을 추가하는 것이 더 쉽고, 맨 앞에 추가하는 것도 쉽다. 물론 이는 순서를 지키지 않아도 되는 경우에만 해당될 것이다.

 

 

※ 다음 코드를 분석해보자.

malloc 은 node 를 저장할 만큼의 크기의 메모리 덩어리를 만들어준다.

node *n 은 node 의 주소를 가진 포인터를 선언한 것이다. 그렇기 때문에 malloc의 반환 값을 n 변수에 넣어서 n이 node를 저장할 수 있는 크기의 메모리 덩어리를 가리키도록 만든다.

즉, n 은 node 를 가리키는 포인터이다. n 은 node * 로 나타낼 수 있는 node 포인터이다. 이 말은 n 은 node 의 주소라는 의미이다.

그리고 malloc 이 주소 값을 반환하기 때문이다.

이것이 바로 "->" 를 사용하는 이유이다.

n 은 node 가 아니기 때문에 n.next 나 n.number 라고 쓸 수 없다. * 를 붙인 뒤에야 . 을 쓸 수 있게 된다.

그리고 이를 간단하게 n->number, n->next 라고 써주는 것이다.

 

 

자료출처 : 부스트코스 - https://www.boostcourse.org/cs112/lecture/119039?isDesc=false