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

3. 연결 리스트(Linked List)

 

연결 리스트(Linked List)/Data와 Next(포인터)

 

 

정의

데이터가 순차적으로 연결된 노드들의 집합으로 이루어진 자료 구조.

 

기본 구조

• 데이터 : 저장할 값
• 포인터 : 다음 노드의 주소를 가리키는 포인터
• 첫 번째 노드를 헤드(Head)라고 하며, 가장 마지막 노드의 포인터는 Null을 가리킴

 

종류

• 단일 연결 리스트(Singly Linked List)
• 이중 연결 리스트(Doubly Linked List)
• 원형 연결 리스트(Circular Linked List)

 

특징

• 동적 크기 : 메모리에 필요한 만큼만 노드를 추가할 수 있어 동적 메모리 할당 가능
• 노드 기반의 자료 구조 : 노드(Node)라는 단위로 구성되며, 각 노드는 데이터와 다음 노드에 대한 포인터로 이루어짐
• 비연속적 메모리 할당 : 각 노드가 흩어진 메모리에 저장되고, 포인터로만 연결되기 때문에, 노드 간의 물리적 순서와 상관없이 논리적 순서가 유지됨
• 순차 접근 : 순차 접근(Sequential Access)만 가능하며, 임의 접근(Random Access)가 불가능

 

활용 예시

• 빈번한 삽입과 삭제가 필요한 경우
• 데이터의 크기가 가변적이거나, 미리 예측할 수 없는 경우
• 메모리를 효율적으로 사용해야 하는 상황 (메모리 분할이 필요하거나 배열 크기 변경이 비효율적인 경우)
  스택, 큐 같은 자료 구조의 구현

 

장단점

장점

• 동적 메모리 관리가 가능하여, 데이터의 크기가 가변적일 때 메모리를 효율적으로 사용할 수 있음
• 노드를 연결만 재조정하면 되므로, 배열과 달리 중간에 삽입과 삭제가 효율적

 

단점

• 순차 접근만 가능하여 임의의 인덱스 접근이 불가능하고, 탐색 속도가 느림
• 추가 메모리 사용이 필요하고, 각 노드에 포인터를 저장해야 하므로 배열보다 메모리를 더 사용해야 함

 

연산과 시간 복잡도

연산	설명	시간 복잡도
접근 (Access)	특정 인덱스의 값에 접근	O(n)
탐색 (Search)	특정 값을 가진 노드를 찾음	O(n)
삽입 (Insertion)	처음 삽입 : 리스트의 처음에 삽입 중간/끝 삽입 : 삽입 위치까지 이동	처음: O(1) 중간/끝에: O(n)
삭제 (Deletion)	처음 삭제 : 리스트의 처음 삭제 중간/끝 삭제 : 삭제할 위치까지 이동	처음: O(1) 중간/끝에서: O(n)

 

 

배열과 연결 리스트의 중간 삽입/삭제

 

• 배열과 연결 리스트는 중간 삽입/삭제 시 시간 복잡도가 동일하지만, 연결 리스트가 유리한 점은 메모리 이동과 복사 비용이 없다.
• 배열은 연속된 메모리에서 작업을 하기 때문에 중간 삽입/삭제가 복잡하고 성능 저하가 발생할 수 있는 반면, 
• 연결 리스트는 비연속적인 메모리에서 작업을 하기 때문에 데이터 이동이나 복사 없이 포인터만 수정하여 빠르게 작업을 처리할 수 있다.