[자료구조] 연결 리스트의 이해(1)

[자료구조] 연결 리스트의 이해(1)

연결 리스트는 크게 배열 기반 연결 리스트와

연결 리스트 기반 연결 리스트가 있는데

우리가 흔히 사용하는 연결리스트는 후자이기 때문에

연결 리스트 기반의 연결 리스트에 대해 알아보도록 하겠다.

들어가기에 앞서 배열과의 비교가 우선시 되어야 할 것같다.

배열이라 함은 기본 제공되는 상당히 훌륭한 자료구조이다.

배열의 가장 큰 장점 중 하나는 index를 통한 순차접근이다.

배열의 가장 큰 단점 중 하나는 크기가 결정되어야 한다는 것인데

이는 매우 큰 부담으로 작용한다. 물론 크기를 바꿀 수 있는 방법이 없는 것은

아니지만, 그에 따른 비용이 만만치 않기 때문에 큰 단점이라 할 수 있다.

때문에 배열보다 좀 더 유연하고 순차 접근을 훌륭히

 수행할 수 있는 것이 필요한데 이것이 바로 연결 리스트이다.

malloc를 이용한 동적할당이 기본이 되어야하고,

할당된 메모리를 어떻게 접근하고 관리할 것인가가

연결 리스트를 이해하는 것의 가장 큰 이슈가 될 것이다.

1. 구조체의 이해

2. 동적 할당 (malloc)

3. 어떻게 연결할 것인가?

4. 어떻게 순차 접근할 것인가?

1. 구조체의 이해

힙에 할당되어 저장되는 자료를 우리는 노드(node)라고 부른다.

노드는 C에서 구조체 변수이다. (기본 제공 타입이 아님)

이렇듯 노드에는 데이터를 담을 공간과

다음 노드를 가리킬 구조체 포인터를 가지고 있다.

2. 동적 할당

malloc, free는 C언어 기본서 참고

3. 어떻게 연결할 것인가?

들어가기에 앞서 노드의 연결과 참조를 위한 핵심을 훑어보자.

next는 현재 노드의 다음 노드를 가리키고 있다.

이렇게 노드들을 쭉 연결 한다면 비엔나 소시지처럼

연결된 모양이 될 것이고, 결과적으로는 첫 노드의

주소값만 알고 있다면 모든 노드를 탐색할 수 있다.

n1,n2는 노드이고 각각의 데이터를 가지고 있다.

next라는 구조체 포인터는 자신의 다음 노드를 가리키도록 한다.

( 주의할 점은 꼭 현재 노드의 뒤에만 새로운 노드가 올 수 있는 것은 아니다. )

현재 노드의 앞 뒤 어느 곳에서든 노드가 추가될 수 있어야 한다.

4. 어떻게 순차 접근을 할 것인가?

n1의 next는 자신의 다음 노드를 가리키고 있기 때문에

*를 사용한다면 자신의 다음 노드에 접근할 수 있다.

연결 리스트와 배열과의 차이점 그리고 연결 리스트를

구현하기에 앞서어떠한 핵심을 공략해야하는지에 대해

간단하게 알아보았다. 다음 포스팅부터는 이슈들을 하나하나

 해결해가며 연결 리스트를 구현해 보도록 하겠다.