연결리스트

연결리스트

연결 리스트의 필요성

1. 배열을 사용하는 경우 메모리 공간이 불필요하게 낭비될 수 있음

2. 이때 연결 리스트를 사용하여 메모리 낭비 현상 방지 가능

 

배열 기반 리스트의 특징

1. 배열로 만들었으므로 특정한 위치의 원소에 즉시 접근할 수 있다는 장점이 있음

2. 데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점

3. 원하는 위치로의 삽입이나 삭제가 비효율적

 

연결 리스트

1. 구조체와 포인터를 함께 사용하여 구현

2. 중간지점에 노드를 추가하거나 삭제할 수 있어야 함

3. 필요할 때마다 메모리 공간을 할당받음

 

단일 연결 리스트

• 일반적으로 연결리스트의 시작노드를 Head라고 함

• 끝 노드의 next에는 null이 들어갈 수 있도록

 

연결 리스트 삽입

 

연결 리스트 삭제

연결 리스트의 특징

• 삽입과 삭제가 배열에 비해서 간단하다는 장점이 있음

• 배열과 다르게 특정 인덱스로 즉시 접근하지 못함 (원소를 차례대로 검색해야 함)

• 추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비

 

양방향 연결 리스트

• 양방향 연결 리스트는 Head와 Tail을 모두 가짐

•  

 

연결 리스트 삽입

연결 리스트 삭제