[lecture] 연결 자료구조

연결 자료구조(Linked Data Structure)

연결 자료구조란, 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조로, 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순가 연결되기 때문에 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다. 또한, 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현하기 때문에 크기 변경이 유연하고 더 효율적으로 메모리를 사용할 수 있다. 

여기서 연결리스트란, 리스트를 연결 자료구조로 표현한 구조인데, 연결하는 방식에 따라 단순연결 리스트와 원형 -, 이중 - , 이중 원형 - 이 존재한다.

순차 자료구조의 문제점은 1. 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해 원소들을 이동시키는 추가적인 작업과 시간이 소요된다. 2. 배열을 이용해 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가진다. 3. 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방법이 필요하다. 는 점이다.

노드란, 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조를 말한다. 이는 원소의 값을 저장하는 데이터 필드와 다음 노드의 주소를 저장하는 링크 필드로 이루어져 있다. 데이터 필드는 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성되고, 링크 필드는 포인터 변수를 사용하여 주소값을 저장한다. 

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

원형 연결 리스트란, 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트를 말한다. 따라서, 링크를 따라 계속 순회한다면 이전 노드에 접근이 가능하다.

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

이중 연결 리스트란, 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트를 말한다. 이 노드는, 두 개의 링크 필드와 한 개의 데이터 필드로 구성되어 있는데, llink(left link) field는 왼쪽 노드와 연결하는 포인터이며, rlink(right link) field는 오른쪽 노드와 연결하는 포인터이다.