[Data Structure] 연결 리스트(Linked-List) 구조

연결 리스트 (Linked-List)

- 각 상자들을 연결하는 줄 : 포인터로 구현

- 각 상자들 : 노드 

- 필요할 때마다 동적 메모리 할당(malloc())을 통해 노드 생성

 

- 노드 : 데이터 필드/링크 필드로 구성

- 데이터 필드 : data(값) 존재

- 링크 필드 : 다른 노드를 가리키는 포인터 존재 → 포인터를 이용하여 다음 노드에 접근

 

- 첫 번째 노드를 알면 전체 노드에 접근 가능

- 첫 번째 노드를 가리키는 변수 : 헤드 포인터 (head pointer)

- 마지막 노드의 링크 필드 = NULL (더 이상 연결된 노드 X)

 

- 실제 메모리 안의 물리적 순서 ≠ 리스트 안의 논리적 순서

 

 

연결 리스트의 장단점 (삽입/삭제)

장점

- 삽입/삭제 시 데이터를 이동할 필요가 없다

- 연속된 메모리 공간이 필요가 없다 (필요할 때마다 동적으로 노드 생성)

- 데이터 개수의 제한이 없다

 

단점

- 구현이 어렵다

- 오류가 발생하기 쉽다

 

 

연결 리스트의 종류

---

[Data Structure] 단순 연결 리스트

 

[Data Structure] 원형 연결 리스트

 

 

[Data Structure] 이중 연결 리스트