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

자료구조(Data Structure)

자료구조 종류

• 순차 리스트
  • 배열 / 행렬 / 레코드
  • 스택 / 큐 / 데크
• 연결 리스트
  • 단일 연결 리스트
  • 원형 연결 리스트
  • 이중 연결 리스트
• 트리
  • 일반 트리
  • 이진트리

선형 리스트

• 각 데이터가 배열과 같이 연속되는 기억 장소에 순차적으로 저장되는 자료 구조
• 1차원 배열과 비슷한 구조이지만, 원소의 개수가 유동적
• 원소를 나열한 순서가 원소들의 순서가 됨
• 원소들의 논리적인 순서와 메모리에 저장하는 물리적인 순서가 같은 구조로 되어 있음
• 순차 자료구조에는 원소들이 순서대로 연속 저장되어 있기 때문에 시작 위치와 원소의 길이를 알면 특정 원소의 위치를 알 수 있음

 

리스트에서 처리할 수 있는 연산

• 길이: 리스트의 길이를 구하는 연산
• 접근: 리스트의 내용을 조사하거나 변경하기 위해 위치를 찾는 연산
• 검색: 리스트의 노드들 중에서 필요한 노드(i번째)를 찾는 연산
• 저장: i번째 노드에 새로운 값을 기억시키는 연산
• 삽입: 리스트에 새로운 노드를 삽입시키는 연산
• 삭제: 리스트에서 노드를 제거하는 연산
• 복사: 리스트의 전체 또는 일부를 복사하여 새로운 노드(리스트)를 만드는 연산
• 정렬: 어떤 기준으로 리스트를 정렬(오름차순/내림차순)하는 연산
• 병렬: 둘 또는 그 이상의 리스트를 하나의 리스트로 합치는 연산
• 분리: 한 리스트를 둘 또는 그 이상의 리스트로 나누는 연산

선형 리스트의 특징

• 기억 장소를 최대로 이용할 수 있는 구조
• 기억 장소에 저장되어 있는 정보들의 삽입, 삭제, 교환 등의 변화 시에는 복잡한 처리 필요
  • 삽입 및 삭제 후에는 리스트를 다시 정리하여 전체 리스트의 순서를 유지하는 작업 필요
  • 자료 이동이 많음
• 따라서, 항목 이동에 관련된 수행 시간을 줄이기 위해 순서 리스트를 비순차적으로 표현하는 것이 필요 - 연결 리스트(Linked list)

 

선형 리스트에 노드 삽입

 

선형 리스트의 단점

• 데이터를 중간에 삽입하거나 중간 데이터를 삭제할 경우 많은 양의 데이터 이동 발생
• 특히 데이터가 많을 경우 이동해야 하는 데이터 수가 더 많아짐
• 크기가 다양하나 여러 개의 선형 리스트들을 조작할 때 각각의 리스트에 대해 최대 크기를 가진 배열을 처음부터 준비해 두어야 하므로 기억 장소 낭비

단점 해결

• 임의의 위치에 데이터를 삽입하거나 삭제가 용이하고 기억 장소를 낭비하지 않는 것
• 삭제와 삽입 연산에 소요되는 시간을 절약하기 위한 새로운 형태의 선형 리스트 필요
• 단일 연결 리스트(singly linked list)

단일 연결 리스트

• 데이터를 연결(linked) 형태로 표현
• 리스트 내의 각 항목들이 순차적으로 저장될 필요 없이 기억 장소 내 어디든 저장되어 있어도 됨
• 다음 항목을 찾기 위해 각 항목들은 다음 항목을 가리키는 포인터를 가짐
• 이 포인터를 링크(link)라고 부름

 

 

 

 

단일 연결 리스트의 특징

• 리스트 각 항목은 기억 장소의 순서대로 위치하지 않고 링크라는 필드를 이용하여 리스트 원소들의 순서를 나타냄
• 리스트 끝에는 더 이상 원소가 없다는 것을 나타내기 위하여 마지막 원소의 링크 필드에 NULL(역슬래시)로 표시

단일 연결 리스트의 기본 연산

• 노드 생성
• 노드 삽입
• 노드 삭제

단일 연결 리스트의 노드 생성

1. 가용 기억 공간 중에서 리스트에 연결할 수 있도록 하나의 노드를 획득
2. 그 노드의 주소를 새로운 포인터에 부여
3. HEAD 포인터가 새로 생성된 노드를 가리키게 함
4. 노드에 데이터 저장

단일 연결 리스트의 노드 삽입

• 리스트에 노드가 하나도 없을 때 새로운 노드 1개를 삽입하는 경우
• 새로운 노드를 가져와서 HEAD가 새로운 노드를 가리키게 하고

• 노드에 데이터 저장

• 새로운 노드의 링크를 필드 값 지정

• 리스트의 앞 노드에 새 노드 연결

단일 연결 리스트의 노드 삭제

• 노드의 상태 확인

• 앞 노드 찾기(삭제할 원소의 앞 노드)

• 앞 노드에 삭제할 노드의 링크 필드값 저장
• 삭제한 노드의 앞 뒤 노드 연결