연결 리스트 (linked list)
연결된 표현 (linked representation)
: 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 표현
=> 포인터를 사용하여 데이터를 연결함
=> 리스트 뿐만 아니라 다른 자료구조 (트리, 그래프, 스택, 큐)등을 구현한는데도 많이 사용됨
연결 리스트
: 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법
=> 상자를 연결하는 줄은 포인터(pointer)로 구현됨
장점
중간에 삽입(삭제)하는 문제가 쉽게 해결됨
데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들엇 쉽게 추가할 수 있음
단점
배열로 구현한 리스트에 비하여 상대적으로 구현하기 어려워서 오류가 나기 쉬움
데이터뿐만 아니라 포인터도 저장해야 하므로 메모리 공간을 많이 사용함
연결 리스트의 구조
노드(node)
: 그림에서의 상자들
데이터 필드와 링크 필드로 구성됨
연결 리스트
: 노드들의 집합
데이터 필드
: 저장하고 싶은 데이터가 들어감 (정수, 구조체같은 복잡한 데이터)
링크 필드
: 다른 노드를 가리키는 포인터가 저장됨 (이 포인터를 이용하여 다음 노드로 건너갈 수 있음)
헤드 포인터
: 연결 리스트마다 첫 번째 노드를 가리키는 변수
=> 연결 리스트에서는 연결 리스트의 첫 번째 노드를 알아야 만이 전체의 노드에 접근할 수 있음
마지막 노드의 링크 필드는 NULL으로 설정됨 => 더 이상 연결된 노드가 없다
연결된 리스트의 노드들은 필요할 때마다 malloc()을 이용하여 동적으로 생성됨
연결 리스트의 종류
3가지 종류의 연결 리스트가 있다.
단순 연결 리스트 (singly linked list)
: 하나의 방향으로만 연결되어 있는 연결 리스트
원형 연결 리스트 (circular linked list)
: 단순 연결 리스트와 같으나 마지막 노드의 링크가 첫 번째 노드를 가리킴
이중 연결 리스트 (doubly linked list)
: 각 노드마다 2개의 링크가 존재