순차 자료구조의 개념

• 구현할 자료들을 논리적 순서로 메모리에 연속 저장하는 구현 방식

• 논리적인 순서와 물리적인 순서가 항상 일치해야 함

• 순차 자료구조 = 배열

순차 자료구조와 연결 자료구조의 비교

구분	순차 자료구조	연결 자료구조
메모리 저장 방식	메모리의 저장 시작 위치부터 빈자리 없이 자료를 순서대로 연속하여 저장한다. 논리적인 순서와 물리적인 순서가 일치하는 구현 방식이다.	메모리에 저장된 물리적 위치나 물리적 순서와 상관없이, 링크에 의해 논리적인 순서를 표현하는 구현 방식이다.
연산 특징	삽입, 삭제 연산을 해도 빈자리 없이 자료가 순서대로 연속하여 저장된다. 변경된 논리적인 순서와 저장된 물리적인 순서가 일치한다.	삽입, 삭제 연산을 하여 논리적인 순서가 변경되어도, 링크 정보만 변경되고 물리적 순서는 변경되지 않는다.
프로그램 기법	배열을 이용한 구현	포인터를 이용한 구현

선형 리스트의 개념

• 선형 순차 리스트

  • 원소를 논리적인 순서대로 메모리에 연속하여 저장하는 순차 자료구조 방식의 선형 리스트

• 선형 연결 리스트

  • 원소를 논리적인 순서대로 연결하여 구성하는 연결 자료구조 방식의 선형리스트

일반적으로 선형 순차 리스트를 선형 리스트라고 하고,

선형 연결리스트는 연결 리스트라고 함

순차 자료구조(배열)의 문제점

• 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가 작업과 시간 소요

  • 원소들의 이동 작업으로 인한 오버헤드로 원소의 개수가 많고 삽입, 삭제 연산이 많이 발생하는 경우에 성능상의 문제 발생

• 순차 자료구조는 배열을 이용해 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가짐

• 순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방법 필요

연결 자료구조

• 자료의 논리적인 순서와 물리적인 순서가 불일치

  • 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식

    • - 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음

  • 여러개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현

    • - 크기 변경이 유연하고 더 효율적으로 메모리를 사용

• 연결 리스트

  • 리스트의 연결 자료구조로 표현

  • 연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결리스트, 이중 원형 연결 리스트로 나뉨

단순 연결 리스트

• 단순 연결 리스트의 개념

  • 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가짐

• 단순 연결 리스트로 노드를 삽입하는 방법

  1. 삽입할 노드를 준비한다.

  2. 새 노드의 데이터 필드에 값을 저장한다.

  3. 새 노드의 링크값을 지정한다.

  4. 리스트의 앞 노드에 새 노드를 연결한다.

• 단순 연결 리스트로 노드를 삭제하는 방법

  1. 삭제할 노드의 앞 노드를 찾는다.

  2. 앞 노드에 삭제할 노드의 링크 필드값을 저장한다.

  3. 삭제한 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다.

원형 연결 리스트

• 원형 연결 리스트의 개념

  • 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트

    • 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 구성

    • 링크에 따라 계속 순회하면 이전 노드에 접근 가능

이중 연결 리스트

• 이중 연결 리스트의 개념

  • 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

  • 이중 연결 리스트의 노드 구조와 구조체 정의

    • llink(left link) 필드: 왼쪽 노드와 연결하는 포인터

    • rlink(right link) 필드: 오른쪽 노드와 연결하는 포인터

• 이중 연결 리스트에서 노드를 삽입하는 방법

  1. 삽입할 노드를 준비한다.

  2. 새 노드의 데이터 필드에 값을 저장한다.

  3. 새 노드 왼쪽 노드의 오른쪽 링크 필드(rlink)에 있던 값을 새노드의 오른쪽 링크 필드(rlink)에 저장한다.

  4. 왼쪽 노드의 오른쪽 링크 필드(rlink)에 새 노드의 주소를 저장한다.

  5. 새 노드 오른쪽 노드의 왼쪽 링크 필드(llink)에 있던 값을 새노드의 왼쪽 링크 필드(llink)에 저장한다.

  6. 오른쪽 노드의 왼쪽 링크 필드(llink)에 새 노드의 주소를 저장한다.

  7. 노드를 순서대로 연결한다.

• 이중 연결 리스트에서 노드를 삭제하는 방법

  1. 삭제할 노드의 오른쪽 노드와 왼쪽 노드를 찾는다.

  2. 삭제할 노드의 오른쪽 노드의 주소를 삭제할 노드의 왼쪽 노드의 오른쪽 링크 필드에 저장한다.

  3. 삭제할 노드의 왼쪽의 주소를 삭제할 노드의 오른쪽의 왼쪽 링크 필드에 저장한다.

  4. 노드를 순서대로 연결한다.