[자료구조] 5. 연결리스트

01. 리스트의 개념

 

🔸리스트와 배열 개념 비교

 

• 배열: 논리적인 순서와 물리적인 순서가 같음
• 연결 리스트: 논리적인 순서와 물리적인 순서가 같지 않음
  • 개발자가 머릿 속에 있는 데이터 순서와 메모리에 적재된 순서는 다르지만 실제로 데이터를 접근할 때는 순서대로 접근

 

 

 

 

 

 

 

✅ 리스트

• 어떤 정의에 의해서 결정된 논리적인 순서의 나열

 

• 리스트의 순서: 데이터가 저장되는 물리적인 위치와 상관없이 원소들간의 논리적인 순서만 유지함
  • ↔️ 배열의 순서: 배열은 인덱스로 표현되는 순서가 배열 원소의 메모리 공간(주기억 장치, DDR)에서의 물리적인 위치를 의미함

 

• 리스트의 구현 방법
  1. 포인터를 이용한 리스트의 구현 방법: 원소값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 함께 구현하는 방법 => 연결리스트
  2. 배열을 이용한 리스트의 구현 방법

 

 

 

 

 

 

 

---

02. 배열을 이용한 리스트의 구현

 

예) 배열을 이용한 리스트의 구현과 원소 삽입/삭제

구현해야 할 리스트를 3.1운동(1919), 대한 독립(1945), 6.25(1950), 서울 올림픽(1988)의 순서라고 정의한다면

 

 

▪️ 리스트 구현

리스트 = {1919, 1945, 1950, 1988}

 

 

 

 

▪️ 리스트 원소 삽입

리스트 = {1919, 1945, 1950, 1988} 에 1936년에 '애국가 작곡'을 삽입한다면?

• 배열의 확장
  • 초기 배열 선언에서 크기를 충분히 크게 한다면 배열의 추가 확장은 피할 수도 있지만! 원소를 리스트의 중간에 삽입하기 위해서는 리스트의 원소값을 하나씩 뒤로 밀어야하는 상황이 발생함

 

 

 

 

▪️ 리스트 원소 삭제

리스트 = {1919, 1936, 1945, 1950, 1988} 에 1936년에 '애국가 작곡'을 삭제한다면?

 

• 모든 원소를 앞으로 당겨야함

 

 

 

 

 

 

🔸배열을 이용한 리스트의 원소 삽입/삭제

• 배열로 구현된 리스트는 원소의 순서가 연속적인 물리적 주소에 저장됨
  • → 원소를 삽입/삭제하기 위해서는 해당 원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 앞으로 당겨야 됨
  • → 리스트 원소값의 이동은 원소 수가 많을수록 프로그램 수행 시간을 증가시킴

 

 

 

🔸 배열을 이용한 리스트의 원소 삽입/삭제 시 발생하는 문제점

• 리스트의 원소 삽입은 프로그램의 실행 중에 메모리 할당을 필요로 하는 경우도 발생시킴
• 배열을 이용한 리스트의 구현은 실제 IT서비스 환경에서는 자주 사용되지 않고 있음
• 자료의 삽입과 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발

 

 

 

 

 

 

 

---

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

 

✅ 노드의 구조

• 노드(node): 리스트의 데이터 요소(원소, 값) + 다음 원소를 지시하는 포인터(주소, 링크(link))

 

 

 

🔸연결 리스트의 논리적 순서와 실제 메모리 표현

 

 

 

 

 

 

 

---

04. 포인터 변수

 

🔸노드 생성

• 정수값(data)과 링크(link)로 구성된 노드의 생성

 

 

 

🔸포인터의 할당과 반환 예

• malloc: 프로그램 실행 중에 내가 필요할 때마다 메모리를 받는 것. 배열 할당과 다름

 

 

 

 

 

 

 

 

---

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

 

🔸 연결 리스트에서 노드의 삭제

• 연결 리스트의 초기 모습

 

• 연결 리스트의 노드 삭제

 

• 연결 리스트의 삭제 결과

 

 

▪️ 리스트의 원소 삭제 연산 단계

1. 삭제할 노드의 선행 노드의 링크 필드를 삭제할 노드의 후행 노드를 가리키게 한다
2. 삭제할 노드를 메모리에 반환한다

 

 

 

 

 

🔸연결 리스트에서 노드의 삽입

• 연결 리스트의 초기 모습

 

• 연결 리스트의 삽입 노드

 

• 연결 리스트의 삽입 결과

 

 

 

▪️ 연결 리스트의 원소 삽입 연산 단계

1. 메모리 공간을 할당 받고 삽입할 내용을 저장하여 삽입할 x노드를 생성한다
2. x노드의 링크 부분이 후행 노드가 될 j노드를 가리키게 한다
3. 삽입될 x노드의 선행 노드가 될 i노드의 링크 필드가 x노드를 가리키게 한다