C/C++ 연결 리스트(Linked List) (1)

개요

추상적 자료형인 리스트를 구현한 자료구조로, 일반적인 리스트는 stack 또는 heap에 연속적인 메모리 구조에 데이터를 집어넣는 방식이다. 반면에, 연결 리스트는 리스트의 요소를 담고 있는 데이터 덩어리인 Node를 기준으로, Node를 포인터를 이용해 데이터를 이어서 구현한 리스트이다. Node에는 다음의 요소 Node를 향한 포인터를 담고 있는 것이 큰 특징이다. 예를 들어 한 반에 있는 학생들의 자료를 저장한다면, 학생 하나하나의 신상명세 자료를 노드로 만들고, 1번 학생의 신상명세 자료에 2번 학생 신상명세가 어디있는지 표시를 해 놓는 방식이다. 쉽게 생각하면 자료를 비엔나 소시지마냥 줄줄이 엮어놓은 것이다.

연결 리스트 vs 리스트

연결 리스트

• 데이터 길이에 있어 유연하다. 데이터를 넣을 필요가 있을 때, heap공간에 노드를 생성해 잇기만 하면 된다.

• heap공간에만 생성할 수 있다. 포인터를 사용하기 때문에 stack에 저장하지 않는다.

• 중간에 데이터를 삽입, 데이터 삭제가 용이하다. 노드를 생성해서 이어 붙이거나, heap에서 메모리를 해제하기만 하면 된다.

• 데이터에 접근하기 위해서는 무조건 처음 노드부터 포인터를 통해 traversing해야 하기 때문에 데이터 탐색에 있어 일반 리스트에 비해 속도/효율이 좋지 않다.

리스트

• 데이터를 stack에 생성하거나 heap 생성할 수 있으며, 연속적인 메모리를 차지한다.

• 데이터 길이를 처음 선언할 때 정할 수 있어, 동적으로 데이터의 양이 변할 때, 리스트의 공간이 남거나, 부족한 현상이 발생한다.

• 데이터를 중간에 삽입하거나, 삭제할 때, 생성, 삭제 후, 인덱스를 변화시켜야 하는 불편함이 있다.

• 데이터 접근이 용이하다. 인덱스로 접근하면, 코드 한 줄로 접근할 수 있어 속도/효율 면에서 좋다.

연결 리스트의 종류

노드 끼리의 연결 구조에 따라 3가지 종류로 나뉜다.

1. 단순 연결 리스트(Singly Linked List)

2. 이중 연결 리스트(Doubly Linked List)

3. 순환 연결 리스트(Circular Linked List)

단순 연결 리스트는 데이터를 한 방향으로만 연결하여, 처음과 끝이 존재하는 형태이다.

이중 연결 리스트는 노드가 양 방향으로 연결되어 있다. 순환 연결 리스트는 처음과 끝이 이어져서 끝의 다음 포인터가 처음이 되는 형태이다.

연결 리스트의 필요 구현 사항

1. Node

2. create함수-연결 리스트 생성

3. Display함수-연결 리스트 요소 프린트

4. Count함수-리스트의 요소의 수 계산

5. Search함수-해당 요소의 위치/노드 반환

6. Insert함수-요소를 추가로 필요한 위치에 추가

7. Delete함수-지우고 싶은 요소를 삭제

8. Reverse함수-요소의 순서를 반전

추가적인 함수는 해당 리스트 유형에 따라 유연하게 작성해볼 것이며, 위의 함수들이 필수적인 함수들이라고 생각된다.

연결 리스트의 기본적인 구조

위의 사진은 연결 리스트의 가장 기초적인 구조를 시각화 한 것이다. 앞으로의 구현은 위의 그림을 기반으로 작성하며, 함수 구현마다 원리를 그림으로 모두 그려 올리지 못하기에 위의 사진을 참고하여 코드를 분석해주길 바란다.

다음 글에서, 단순 연결 리스트부터 순차적으로 구현해보도록 하겠다.