연결리스트

연결리스트 (Linked List)

특징

1. 데이터를 선형적으로 저장 및 처리한다.

2. 삽입과 삭제가 많은 경우 효율적이다.

3. 리스트의 중간 지점에 노드의 추가/삭제가 가능하여야 한다.

4. 메모리 공간을 미리 할당하는 배열을 보완하여 공간 낭비를 감소시킨다.

✚ 배열 기반의 리스트

• 장점 : 즉시 접근이 가능하다.

• 단점 : 삽입 삭제가 비효율적이며 메모리 공간을 미리 할당한다.

종류

단일 연결리스트

• 단일 연결리스트는 가장 앞의 노드를 가르키는 HEAD를 갖는다.

• 각 노드별로 동적 메모리를 할당하여야 하며, 각 노드를 연결시켜주어야 한다.

####︎︎ 노드 삽입

• HEAD 다음에 노드를 삽입한다고 가정

• ‘HEAD의 *next’가 ‘삽입 노드의 값’을 가리키게 한다.

• ‘삽입 노드의 *next’가 ‘기존 노드의 값’을 가리키게 한다.

노드 삭제

• HEAD 다음에 위치한 노드를 삭제한다고 가정

• ‘HEAD의 *next’가 ‘삭제될 노드의 다음 값’을 가리키게 한다.

• 삭제된 노드의 동적 메모리를 해제하여 메모리 누수를 방지한다.