4.연결리스트 - 연결리스트

앞장에서 배열을 이용한 리스트 구현에 대해서 배웠다. 요약하자면 아래와 같다.

 

1.ADT  (Abstract Data Type) 추상 자료형에 대한이해

 

2.리스트 자료구조의 특성과 활용

 

3.리스트 종류

-순차 리스트 : 배열을 기반으로 구현된 리스트 

-연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트 

 

4.배열 기반 리스트의 단점 

-배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다. 

-삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다. 

 

5.배열 기반 리스트의 장점 

-데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다. 

 

 

배열과 관련된 예제를 보자.

 

위의 예제를 보면 배열의 단점을 알 수 있다. 

 

"배열은 메모리의 특성이 정적이어서(길이의 변경이 불가능해서) 메모리의 길이를 변경하는 것이 불가능하다."

 

또한 "0을 입력하지 않고 계속 자연수만 입력하면 배열의 길이를 넘어서는 문제가 발생한다. 즉, 정적인 배열은 필요로 하는 메모리의 크기에 유연하게 대처하지 못한다. 그래서 등장한 것이 동적인 메모리의 구성이다."

 

 

참고로 연결리스트를 이해하기 위해서는 malloc 함수와 free 함수를 기반으로 하는 메모리의 동적 할당에 대해서 이해를 하고 있어야 한다. 

 

 

위 구조체의 멤버 next는 Node형 구조체 변수의 주소 값을 저장할 수 있는 포인터 변수다. 이 변수는 바구니(Node)와 바구니를 연결할 목적으로 선언된 멤버다. 이 멤버로 인해서 모든 Node형 구조체 변수는 다른 Node형 구조체 변수를 가리킬 수 있으므로 , 그림처럼 연결이 가능하다. 

 

요약하면 연결리스트는 아래와 같이 정의할 수 있다.

 

"필요할 때마다 바구니의 역할을 하는 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다"

 

 

예제 - DLinkedList.h

 

예제 - DLinkedList.c

 

예제 - main.c

 

 

04 연결 리스트(Linked List) 2.pdf

1.39MB

 

0902.zip

0.03MB

 

 

 

 

 

참고: 윤성우의 열혈 자료구조