[자료구조] 연결리스트(Linked List)

Linked List

링크를 가진 리스트

List의 의미 : 순서가 있는 구성

가장 쉽게 접할 수 있는 기본적인 List는 배열을 들 수 있습니다.

즉 Linked List는 순차적으로 다른 데이터를 참조할 수 있는 구조로 데이터를 관리합니다.

C언어 / C++ 에서의 자료구조는 데이터와 다음 노드를 가리키는 포인터를 가지지요.

C와 C++의 Linked List 구조

node기반의 리스트로, 각 node는 데이터와 다음 노드의 주소정보를 가집니다.

여러가지 방법으로 구현을 할 수 있으나, 가장 기초적인 형태는 다음과 같습니다.

Linked List의 장단점

장점 

노드의 포인터를 통해서 모든 데이터의 참조가 가능하다.

링크 이동을 통한 유연한 변경이 가능하다.

단점

데이터의 위치를 알아도 바로 접근할 수 없다.

정렬속도가 느리다.

[출처] [자료구조] 연결리스트 ( Linked List)|작성자 HJ

 

---

1. 단일 연결리스트 기본 구조

헤드로부터 시작해 연속적으로 다음 노드를 가리키며

마지막 노드는 NULL을 가리킵니다.

2. 중간에 새로운 노드 삽입

노드삽입시 기존의 연결이 끊어지지 않도록 순서에 주의해야합니다.

따라서 삽입할 노드가 다음위치의 노드를 가리키게 하고, 

이전위치의 노드가 삽입되는 노드를 가리키게 합니다.

3. 특정 노드 삭제

노드의 삭제 또한 기존의 연결이 끊어지지 않도록 주의해야하며,

삭제대상 노드를 잃어 memory leak이 일어나지 않도록 주의해야합니다.

우선 임시변수로 삭제할 노드를 가리켜서 잃지 않도록하고,

이전 노드가 다음 노드를 가리키도록 합니다.

만일 노드가 포함한 데이터가 동적할당되었다면

이 또한 할당해제를 잊지 않고 우선 할당해제 해주어야 memory leak이 일어나지 않으며

최종적으로 삭제할 노드도 할당해제함으로 마무리 합니다.

[출처] [자료구조] 단일 연결리스트 구조 - 삽입, 삭제 (Single Linked List)|작성자 HJ