연결 자료구조와 연결 리스트(1)

순차 구조는 데이터에 빠르게 접근할 수 있다는 장점이 있으나, 중간에 데이터를 삽입하거나 삭제할 때마다 줄을 다시 맞추기 위해 많은 데이터를 옮겨야 하는 비효율적인 문제가 있습니다.이 문제를 해결하기 위해 '연결 자료구조'와 예시인 '연결 리스트'에 대해 글을 작성합니다.

연결 자료구조

연결 자료구조는 순차 자료구조와 반대의 아이디어에서 출발합니다. 데이터를 메모리상에 나란히 놓을 필요 없이, 흩어져 있는 데이터들을 주소(링크)를 이용해 논리적으로 연결하는 방식입니다.

 

각 데이터는 '다음 장소'에 대한 정보(다음 데이터의 메모리 주소)를 가지고 있습니다. 이 덕분에 중간에 새로운 데이터가 추가되어도 이전 데이터의 목적지만 바꿔주면 전체 흐름에 자연스럽게 끼어들 수 있습니다. 데이터를 일일이 옮길 필요가 없는 것입니다.

• 핵심 : 논리적 순서와 물리적 저장 순서가 다르다.
• 장점 : 데이터 삽입/삭제가 매우 빠르고, 필요한 만큼만 메모리를 사용하므로 유연하다.

연결 리스트의 기본 단위(노드)

연결 리스트는 '노드'라는 기본 단위들이 사슬처럼 연결된 구조입니다. 각각의 노드는 두 부분으로 구성됩니다.

1. 데이터 필드(Data Field) : 저장하고 싶은 실제 데이터(숫자, 문자 등)가 들어가는 공간입니다.
2. 링크 필드(Link Field) : 다음 노드가 어디에 있는지 그 '메모리 주소'를 저장하는 포인터 공간입니다. 이 링크가 바로 노드들을 연결하는 끈 역할을 합니다.

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

단순 연결 리스트는 기본적인 형태의 연결 리스트입니다. 각 노드가 하나의 링크 필드를 가져서, 다음 노드로만 이동할 수 있는 단방향 구조를 가집니다. 리스트의 가장 마지막 노드는 더 이상 가리킬 곳이 없으므로, 링크 필드에 NULL을 저장하여 리스트의 끝임을 표시합니다.

• 삽입 연산 : 데이터를 추가할 때, 이전 노드와 다음 노드 사이의 링크만 조정하면 됩니다. 새 노드를 만들고, 이전 노드의 링크가 새 노드를, 새 노드의 링크가 기존의 다음 노드를 가리키도록 연결을 바꿔주는 과정입니다.
• 삭제 연산 : 데이터를 삭제할 때도 같습니다. 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 직접 가리키도록 링크를 건너뛰게 만들어줍니다.

원형 연결 리스트 (Circular Linked List)

원형 연결 리스트는 단순 연결 리스트의 마지막 노드가 NULL을 가리키는 대신, 리스트의 가장 첫 번째 노드를 가리키는 구조입니다. 이름처럼 노드들이 둥글게 원형으로 연결되어 있어 끝이 존재하지 않습니다.

이 구조는 마지막 노드에서 다시 첫 노드로 바로 이동해야 하는 작업이나, 리스트를 계속 순회해야 하는 경우에 매우 유용합니다.

연결 리스트는 순차 리스트의 단점을 극복하기 위해 등장한 중요한 자료구조입니다. 링크를 변경하는 것만으로 삽입과 삭제가 자유롭다는 강력한 장점 때문에, 다양한 알고리즘과 프로그램에서 핵심적인 역할을 담당합니다.