3. 연결 리스트로 구현된 리스트

연결 리스트 (linked list)

연결된 표현 (linked representation)

: 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 표현

=> 포인터를 사용하여 데이터를 연결함

=> 리스트 뿐만 아니라 다른 자료구조 (트리, 그래프, 스택, 큐)등을 구현한는데도 많이 사용됨

연결 리스트

: 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법

=> 상자를 연결하는 줄은 포인터(pointer)로 구현됨 

 

장점

중간에 삽입(삭제)하는 문제가 쉽게 해결됨

데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들엇 쉽게 추가할 수 있음

 

단점

배열로 구현한 리스트에 비하여 상대적으로 구현하기 어려워서 오류가 나기 쉬움

데이터뿐만 아니라 포인터도 저장해야 하므로 메모리 공간을 많이 사용함

---

연결 리스트의 구조

노드(node)

: 그림에서의 상자들

데이터 필드와 링크 필드로 구성됨

연결 리스트

: 노드들의 집합

 

데이터 필드

: 저장하고 싶은 데이터가 들어감 (정수, 구조체같은 복잡한 데이터)

 

링크 필드

: 다른 노드를 가리키는 포인터가 저장됨 (이 포인터를 이용하여 다음 노드로 건너갈 수 있음)

 

헤드 포인터

: 연결 리스트마다 첫 번째 노드를 가리키는 변수

=> 연결 리스트에서는 연결 리스트의 첫 번째 노드를 알아야 만이 전체의 노드에 접근할 수 있음

 

 

마지막 노드의 링크 필드는 NULL으로 설정됨 => 더 이상 연결된 노드가 없다

연결된 리스트의 노드들은 필요할 때마다 malloc()을 이용하여 동적으로 생성됨

 

---

연결 리스트의 종류

3가지 종류의 연결 리스트가 있다.

단순 연결 리스트 (singly linked list)

: 하나의 방향으로만 연결되어 있는 연결 리스트

 

원형 연결 리스트 (circular linked list)

: 단순 연결 리스트와 같으나 마지막 노드의 링크가 첫 번째 노드를 가리킴

 

이중 연결 리스트 (doubly linked list)

: 각 노드마다 2개의 링크가 존재