LinkedList
데이터를 링크로 연결해서 관리하는 자료구조
자료의 순서는 정해져 있지만, 메모리상의 연속성은 보장되지 않는다
노드라는 구조체로 이루어진 자료구조, 노드는 데이터와 다음 데이터의 주소를 담고 있다.
- 장점
- 데이터 공간을 미리 할당 받지 않아도 된다
- 리스트 길이가 가변적이라서 추가,삭제가 용이하다
- 단점
- 주소를 저장하는 추가 공간이 필요하다.
- 연결 정보를 찾는 시간이 필요하기 때문에 접근 속도가 상대적으로 느리다
- 데이터 추가, 삭제 시 앞 뒤 데이터의 연결을 재구성하는 작업이 필요하다
노드 : 데이터 저장 단위로, 값 + 포인터로 구성
LinkedList 연산
작업을 수행하는 위치(head, 중간, tail)에 따라 연결 작업이 다르다.
데이터 추가
- head로 추가할 때
- 추가할 데이터를 담을 노드 생성
- 링크 연결 작업
- head 이전 작업
- tail에 추가할 때
- 추가할 데이터를 담을 노드 생성
- head로부터 끝노드까지 순회
- 끝 노드의 포인터에 생성한 노드의 주소 연결
- 중간에 추가할 때
- 추가할 데이터를 담을 노드 생성
- head로부터 데이터 추가 위치 직전 노드까지 순회
- 링크 연결 작업(이전노드의 포인터를 지금 노드에, 지금 노드의 포인터를 다음 노드의 위치로 연결)
데이터 삭제
- head 위치의 노드 삭제할 때
- 삭제 대상 노드 지정(delete_node)
- head 이전 작업
- delete_node 삭제
- tail 위치의 노드 삭제할 때
- head로 부터 가장 끝까지 순회
- 끝 노드 삭제
- 삭제 이전 노드의 링크 처리
- 중간에 있는 노드 삭제할 때
- head로부터 삭제 대상 노드까지 순회 및 해당 노드(delete_node) 지정
- 삭제 대상 이전/이후 노드의 링크 연결 작업
- delete_node 삭제
구현
- 노드 생성
class Node :
def __init__(self, data):
self.data = data
self.next = None
- 가장 오른쪽에 노드 추가하기
# 가장 오른쪽에 노드 추가하기
def append(self, data):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = None(data)
- 전체 데이터 출력
# 전체 데이터 출력
def print_all(self):
cur = self.head
while cur.next is not None:
print(cur.data, end = ' ')
cur = cur.next
- 원하는 노드 찾기
def get_node(self, index):
count = 0
node = self.head
while count < index:
count += 1
node = node.next
return node
- 중간에 노드 삽입 (헤드인 경우 항상 고려하기!)
def add_node(self, index, value) :
new_node = Node(value)
if index == 0:
new_node.next = self.head
self.head = new_node
return
node = self.get_node(index - 1)
next_node = node.next
node.next = new_node
new_node.next = next_node
- 노드 삭제 (헤드인 경우 항상 고려하기!)
def delete_node(self, index):
if index == 0:
self.head = self.head.next
prev_node = self.get_node(index - 1)
prev_node.next = self.get_node(index) .next (prev_node.next.next)
'알고리즘 &자료구조' 카테고리의 다른 글
| [자료구조/python] 복습 4. Heap (0) | 2022.12.22 |
|---|---|
| [자료구조/Python] 복습 3. Deque (0) | 2022.12.22 |
| [자료구조/Python] 복습 1. Queue, Stack (0) | 2022.12.22 |
| [알고리즘] Union -Find (0) | 2022.07.17 |
| [알고리즘] 백트래킹 (0) | 2021.11.10 |
