자료구조 - 연결리스트[linked list] C언어

연결리스트는 동적배열과 비슷하지만 동적배열에 비해 데이터를 유연하게 삽입, 삭제할 수가 있다. 

동적배열의 경우엔 삽입을 하기위해선 배열의 크기를 체크하고 배열의 공간이 꽉 차있다면 realloc을 하였다. 그리고 삽입, 삭제할 지점 이후의 자료들은 메모리의 이동이 이루어지기 때문에, 삽입시 부자연스럽기도 하다.

동적배열과의 연결리스트의 차이점은

배열의 특성은 메모리공간에서 연속이라는 점이다. 그래서 첨자연산으로 빠른 속도가 보장되지만, 메모리가 연속이어야 하기 때문에, 삽입과 삭제가 번거롭다. 하지면 연결리스트는 메모리상에 연속이지 않아도 된다. 다음데이터에 대한 링크정보를 지니고 있기때문에 가능한 일이다.

2014/02/28 - [프로그래밍/C언어] - 동적배열 자료구조의 시작

2014/03/17 - [프로그래밍/C언어] - 동적배열에서 memmove함수 사용하기 연습 C언어

2014/02/25 - [프로그래밍/C언어] - 구조체 정리 C언어

2014/03/20 - [프로그래밍/C언어] - 자료구조 - 연결리스트[linked list] C언어

2014/03/22 - [프로그래밍/C언어] - 자료구조 큐(Queue) C언어

연결리스트의 구조

가장 간단한 형태의 연결리스트를 표현해 보았다.

값, 그리고 다음값의 정보를 가진 구조체를 가리키는 링크주소를 가진 구조체가 하나의 노드(Node)를 이룬다. 배열의 요소에 대응되는 개념이 노드(Node)다. 이런 노드들이 연속적으로 연결되어 있기 때문에 연결리스트라고 불리운다. 위 그림은 노드의 구성멤버가  값이 하나씩 이지만, 값의 경우 필요한만큼 얼마든지 늘릴 수 있다.

그리고 위 형태처럼 다음구조체만을 가리키는 연결리스트를 단순 연결리스트라고 하고, 자신의 앞뒤 노드 모두 가리키는 구조체를 이중연결리스트라고 한다.

여기서는 단순연결리스트를 먼저 다루겠다.

링크주소를 나타내는 포인터는 자기자신의 구조체타입이다. 이렇게 자기자신의 타입의 포인터를 갖는 구조체를 자기 참조 구조체라고 한다. 주의할점은 자신의 타입의 포인터가아닌 자신의 타입의 구조체를 갖게 된다면, 무한루프에 빠지게 될 것이다.

그러면 본격적으로 삽입과 삭제를 해보도록 하자.

노드를 노드와 노드사이에 넣기 위해서는 우선 노드를 동적으로 생성한뒤 링크주소값만 수정해 넣으면 된다.

삭제시에는 반대로 하면된다.

연결리스트를 사용하기 위해선 초기화를 해야한다. 동적배열을 사용할때 와 마찬가지로 포인터에 동적할당 malloc에 해당하는 작업이다. 초기화를 하기위해서 시작위치의 포인터를 선언해야하는데 기본타입은 사용할 노드의 구조체 포인터타입이 된다.

Node *head;

head노드를 동적할당을 한 후 링크주소에 NULL을 넣었다. next값이 NULL인지를 검사하여 마지막 값인지를 알 수 있다. 그리고 head는 가장 첫번째 노드를 가리키기 때문에 전역적으로 선언하여 언제든지 사용할 수 있게 하였다.

위 초기화를 통해 메모리상에는 한개의 head 노드가 형성되었을 것이다.

이젠 삽입하는 코드를 구현해보자. 삽입할 구조체를 인수로 받고, 함수내에서 새로운 노드를 동적할당을 한 후 인수로 받은 구조체를 동적할당된 공간에 복사하자. 그리고 위해서 말했듯이 링크주소를 수정해주면 될 것이다. 한가지 더 삽입할 위치를 정해야하는데, 삽입할 위치를 기준잡을 노드를 인수로 받도록 하자.

위에 그려진 그림을 참조하여 코드와 비교해보자.

다음은 삭제를 하는 코드를 작성 할 것이다. 삭제는 삽입의 반대다.

삭제도 기준이되는 노드를 가리키는 포인터를 인수로 받게된다. 기준이되는 노드 다음의 노드를 지우므로 기준이되는 노드의 next가 NULL이 되면 지울 값이 없으므로 함수를 종료한다.

연결리스트의 노드들은 이름이 없다. 접근하기 위해서는 이전 노드구조체의 멤버를 통한 링크로 접근할 수 있다. 이렇게 연결리스트는 배열과다르게 첨자연산이아니고 링크주소에의해서 연결되어있다. 그래서 배열은 요소마다 직접 첨자연산으로 접근할 수 있지만, 연결리스는 순회를 해야한다. 다시말해서 5번째 요소를 찾고싶다면 처음부터 시작하여 중간 노드들을 거쳐 5번째까지 올라가야한다.

그런데 for문으로 연속적으로 삽입을 하는 경우 현재 포커싱이되는 노드는 삽입이된 노드가 되어야 할 것이다. 그래야 현재 포커싱이 되는 노드 다음에 새로운 노드를 연결시킬 수 있기 때문이다. 그래서 위에 PutNode함수의 리턴값을 현재 포커싱이 되는 노드로 바꾸자.

리턴값을 Node *로 바꾸고 함수 끝에 return New; 를 추가하면 된다.

그러면 이제 연결리스트에 데이타를 집어 넣어보고 순회를 하여 데이타를 출력시켜보자.

메인함수에 위와 같은 코드를 작성하였다. Target(포커싱이되는 노드)은 PutNode함수에의해서 새로 삽입되는 노드로 갱신된다. for문으로 일련의 데이타를 가진 구조체노드를 10개 만들었다.

이젠 출력을 해볼 것이다. 순회를 처음부터 끝까지 할 것인데, 순회의 처음은 head노드부터 시작하여 마지막은 next값이 NULL인경우로 지정하고 조건을 붙이면 된다. 단 head의value는 쓰레기 값을 가지기 때문에 실제로 값을 값는 첫번째 노드는 head->next가 된다.

다음은 전체 코드다.

전체 노드를 초기화하는 코드는 DelNode()함수를 이용하면된다. head부터 시작해서 리턴값이 false가 나올때 까지루프를 돌리면된다. 연결리스트 중 가장 간단한 코드고, 작성방법에 따라서 얼마든지 변형할 수 있지만, 이 틀을 벗어나지는 않는다.