[자료구조#5, 6] 연결 리스트 & 연결 리스트의 응용

리스트의 개념

리스트 : 일정한 순서(논리적/의미적)의 나열

개발자가 보는 것은 추상화된 데이터

메인 메모리에서는 순서가 다르되 리스트로 구현하면 리스트의 순서는 동일하게 노출

배열은 인덱스로 표현되는 순서는 물리적인 위치와 동일

리스트의 순서 개념은 논리적인 순서

 

구현 방법

포인터

배열

 

배열을 이용한 리스트 구현

배열은 메인메모리와 동일한 순서여야 하여 원소 삽입 시, 원소가 이동하여 이동 시간이 걸림

 

배열의 확장

- 초기 배열 선언에서 충분히 크게 하면 배열의 추가 확장을 피할 수 있다

- 배열의 추가 확장을 위해 하나씩 뒤로 밀어야 하는 상황이 발생

 

배열을 이용한 원소 삽입.삭제

- 원소 순서가 연속적인 물리적 주소에 저장

- 모든 원소를 뒤로 물리거나 앞으로 당겨야만함

- 원소 삽입은 프로그램의 실행 중 메모리 할당을 필요로 하는 경우도 발생

 

포인터를 이용한 리스트 구현

노드 : 리스트 원소(값) + 다음 원소를 가르키는 정보

데이터 요소 (원소, 값)과 리스트의 다음 원소를 지시하는 포인터

1919 => 노드 (데이터)

메모리 주소값 => 주소값 (포인트)

 

 

 

포인터 변수 및 리스트의 삭제/삽입

리스트의 생성 : 정수값 data와 링크로 구성된 노드의 생성

1. 변수를 저장

2. 변수의 공간을 저장

 

 

 

 

연결 리스트에서 노드의 삽입과 삭제

삭제	삽입
삭제할 노드의 선행 노드의 링크 필드를 삭제할 노드의 후행 노드를 가리키게 하여 삭제할 노드를 메모리에 반환

 

 

 

---

연결 리스트의 변형

이중 연결 리스트

- 선행 노드에 접근 불가했던 것을 Rlink를 통해 해결할 수 있는 것

- 선행 노드를 가르키는 링크와 후행 노드를 가르키는 링크를 가짐

 

원형 이중 연결 리스트

- 가장 마지막 노드의 Rlink가 null인 것

- 데이터를 쉽게 삽입/삭제할 수 있음

 

원형 연결 리스트

삽입

 

단순 연결 리스트

어떤 특정 노드의 선행 노드를 찾기 위해 사용

 

 

---

	정답 3
	정답 2
	정답 2
	정답 1
	정답 4