리스트 (선형 리스트 / 단일 연결 리스트)

연결 리스트

• 단일 연결 리스트
• 원형 연결 리스트
• 이중 연결 리스트

 

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

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

 

선형 리스트 (linear list)

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

 

선형 리스트의 특징

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

선형 리스트에 노드 삽입

• 새로운 노드 삽입 시, 원소들을 이동시켜 해당 위치를 비워둔 상태에서 새로운 노드 삽입

선형 리스트의 단점

• 데이터를 중간에 삽입/삭제 시 많은 양의 데이터 이동 발생
• 특히 데이터가 많을 경우 이동해야 하는 데이터 수 증가
• 크기가 다양한 여러 개의 선형 리스트 조작 시, 각각의 리스트에 대해 최대 크기를 가진 배열을 미리 준비해 두어야 함 -> 기억 장소 낭비

→ 문제 해결

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

 

단일 연결 리스트

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

단일 연결 리스트 기억 장소 내의 표현

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

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

 : 노드 생성

단일 연결 리스트의 노드 생성 1 - 리스트에 노드가 하나도 없을 때 새로운 노드 1개를 삽입하는 경우
 - 새로운 노드를 얻어와서 HEAD가 새로운 노드를 가리키게 함
 - 노드에 데이터 저장
 - 새로운 노드의 링크를 NULL로 설정

단일 연결 리스트의 노드 생성 2 - 2개의 노드를 생성
 - 새로운 노드를 얻어와서 HEAD가 새로운 노드를 가리키게 함
 - 첫 번째 노드에 데이터 A 저장
 -  두 번째 노드를 얻어와서 p가 새로운 노드를 가리키게 함
 - 첫 번째 노드와 두 번째 노드 연결
 - 마지막 노드 링크의 링크를 NULL로 설정
 - 두 번째 노드에 데이터 B 저장

 

 : 노드 삽입

리스트 맨 처음에 노드 삽입
 - 새로운 노드 얻어와서
 - 새로운 노드가 두 번째 노드를 가리키고
 - HEAD가 새 노드를 가리키게 함

리스트 맨 마지막에 노드 삽입
 - 새로운 노드를 얻어와서
 - 마지막 노드가 새로운 노드를 가리키고
 - 새로운 노드의 링크로 NULL값을 갖게 함

임의의 노드 사이에 노드 삽입 - 노드1과 노드2 사이에 새로운 노드를 삽입할 경우
 - 새로운 노드를 얻어와서
 - 노드1이 새로운 노드를 가리키고
 - 새로운 노드가 노드2를 가리키게 함

 

 : 노드 삭제

맨 처음 노드 삭제
 : 먼저 노드의 유무 확인 -> 삭제할 노드가 없으면 언더플로우 발생
 : 헤더가 가리키는 첫 번째 노드에 대한 참조를 두 번째 노드로 바꿔줌

맨 마지막 노드 삭제
 : 마지막 노드를 찾아서 삭제
 : 마지막 이전 노드의 링크를 NULL로 설정

중간 노드 삭제 - 노드1과 노드2 사이의 노드를 삭제할 경우
 : 노드1의 링크에 삭제하려는 노드의 링크 값(=노드2의 링크 값)을 저장