자료구조 - Chapter 04

연결 리스트

연결 기반 리스트

연결 리스트 구현을 위해선 'malloc 함수' 와 'free 함수' 기반으로 하는 메모리의 동적 할당에 대한 이해가 필요하다.

기존 정적인 배열은 메모리의 크기에 대해서 유연하게 대처하지 못하기 때문이다.

 

예제 : 간단한 연결 리스트

 

링크드 리스트

ex4-1 simple_linkedlist.c

0.00MB

typedef struct _node{

    int data;

    struct _node * next;

} Node;

#next (구조체 변수의 주소 값을 저장하는 포인터 변수)를 사용하여 링크드 리스트를 구현한다.

이런 노드를 동적 할당을 통하여 연결한다.

 

필요한 주요 변수

• Node * head = NULL; 리스트 머리를 가리키는 포인터
• Node * tail = NULL; 리스트 꼬리를 가리키는 포인터
• Node * cur = NULL; 현재의 위치를 가리키는 포인터

자료 구조 공부법

• 자료 구조의 ADT 정의
• 정의한 ADT 구현
• 구현이 완료된 자료구조의 활용

예제 : 머리 추가

머리 추가 방법

ex4-2 input first_linkedlist.c

0.00MB

단순 연결 리스트의 ADT와 구현

새로운 노드 추가 방법

머리 추가 방법

• 장점 : 포인터 변수 tail의 불 필요
• 단점 : 저장된 순서를 유지하지 않는다

꼬리 추가 방법

• 장점 : 저장된 순서가 유지된다
• 단점 : 포인터 변수 tail 필요

더미 노드(dummy node)

링크드 리스트를 연결 할 때, 유효한 데이터를 지니지 않는 빈 노드를 생성해서 연결해 놓는다.

빈 노드를 설정하면, 처음 추가되는 노드가 구조상 두번째 노드가 되기 때문에 노드의 삭제 조회가 편리하다.

 

예제 : 더미 노드 추가한 링크드 리스트 구현하기

더미 노드 추가

ex4-3 dummynode_linkedlist.c

0.00MB

연결 리스트의 정렬 삽입의 구현

예제 : 정렬 함수를 사용한 연결 리스트 구현

DLinkedList.c

0.00MB

DLinkedList.h

0.00MB

ex4-4 Linkedlist_Sort.c

0.00MB