반응형
1. 단일 연결 리스트
| 구성도 |  |
|
| 개념 | - 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 | |
| 특징 | 노드 연결 | 하나의 포인터로 다음 노드만 연결 |
| 삽입/삭제 | 한 방향 탐색으로 속도 느림 | |
| 메모리 | 노드별 포인터를 위한 메모리 필요 | |
| 구성요소 | Head | 시작점으로 외부에서 리스트 참조시 처음 접근 주소 |
| Tail | 종료점으로 리스트 참조, 처리할 때 끝 주소 | |
| Node | 실제 데이터 저장하는 노드, 다음 노드에 대한 포인터 포함 | |
| 구현 | class Node: def __init__(self, data): self.data = data # 실제 저장되는 데이터 self.next = None # 다음 노드 가르킬 포인터 |
|
- 데이터와 포인터를 갖는 노드를 이용하여 데이터의 삽입 및 삭제가 자유로움
2. 이중 연결 리스트
| 구성도 |  |
|
| 개념 | - 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인트까지 함께 노드에 추가되어 역탐색 가능한 자료구 | |
| 특징 | 노드 연결 | 이전, 다음 노드 모두 연결 |
| 삽입/삭제 | 양방향 탐색으로 효율적 | |
| 메모리 | 포인터 2개 사용으로 2배 | |
| 구성요소 | Head | 시작점, 외부에서 리스트 참조할 때 처음 접근하는 주소 |
| Prev | Previous node Pointer, 이전 노드를 가리키는 포인터 | |
| Data | 실제 데이터를 저장하는 자료 저장소 | |
| Next | Next node Pointer, 다음 노드를 가리키는 포인터 | |
| Node | 구조체로 이전, 다음 노드 포인터와 데이터로 구 | |
| 구현 | class DNode: def __init__(self, data): self.data = data # 실제 저장 데이터 self.prev = None # 이전 노드 포인터 self.next = None # 다음 노드 포인터 |
|
- 전후 방향 어느 쪽으로도 순환이 가능한 효율적인 연결 리스트
3. 단일 연결 리스트의 삽입과 삭제 알고리즘
가. 단일 연결 리스트 삽입 알고리즘
| 구분 | 설명 | |
| 개념도 |  |
|
| 알고리즘 | 1) | 삽입할 데이터 노드 2 준비 |
| 2) | 노드1이 노드2 가리키도록 노드1 포인터 수정 | |
| 3) | 노드2가 노드3 가리키도록 노드2 포인터 수정 | |
| 4) | 추가된 노드2가 마지막일 경우 NULL 가르킴 | |
| 코드 | new_node = Node(data) # 새로 삽입할 노드2 생성 new_node.next = prev_node.next # 노드2 포인터로 노드3 가르키기 prev_node.next = new_node # 노드1 포인터로 노드2 가르키기 |
|
나. 단일 연결 리스트 삭제 알고리즘
| 구분 | 설명 | |
| 개념도 |  |
|
| 알고리즘 | 1) | 노드2를 가리키던 노드1이 노드3 가리키도록 포인터 변경 |
| 2) | 노드2 데이터를 메모리에서 삭제 | |
| 코드 | node_1.next = node_1.next.next # 노드1이 노드3 가리키도록 변경 | |
반응형