Linked List가 배열과 어떻게 다른지 비교하면 재밌을 것 같아서 오늘의 주제는 연결리스트이다.
- 개념 이해하기
- 구조 이해하기
- 특성 알아보기
- 비슷한 다른 자료형이랑 뭐가 다른지 비교해보기
- crud 어떻게 하는지 이해하기
- 활용 방향
- 수도 코드 작성해보기
- 구현 코드 작성해보기(임계시간설정필)
1. 개념 이해하기
추상적인 개념을 아래의 사이트에서 잘 설명해주고 있다.
https://opentutorials.org/module/1335/8821
2. 구조 이해하기
3. 특성 알아보기
ArrayList의 장단점
- 연속되는 항목들이 포인트로 연결되어 있음.
- 마지막 항목은 Null을 가리키고 있음. (마지막이라 연결한 노드가 없기 때문)
- 프로그램이 수행되는 동안 크기가 동적으로 커지거나 작아짐.
- 메모리 공간 낭비가 적지만 포인터 메모리가 필요함.
- 배열에 비해 데이터의 추가와 삽입에 용이.
- 단방향(양방향이라도) 순차적으로 탐색하지 않으면 요소에 접근이 불가하기 때문에 탐색 속도가 떨어짐.
- 데이터를 추가하는 건 객체 할당임.
- 링크를 끊어 버리면 데이터가 삭제되기 때문에 (JS기준) 만약 head에서 노드를 전체 삭제하고 싶다면 head에 있는 링크를 끊어 버리기만 하면 된다.
from https://velog.io/@riceintheramen/Linked-list
5번 - 왜그런지 알아보자. 연결되어 있는 구조이기 때문에 원소를 탐색하는데 비효율적이지만 배열보다 삽입 삭제에 용이하다.배열은 중간에 어떤 원소를 삭제하면 뒷 요소들을 전부 이사해줘야 하는데(깊은 복사) 이 깊은 복사는 시간이 많이 든다. 그에 비해 연결리스트는 중간에 어떤 원소를 삭제하면 삭제한 요소의 뒷 요소와 삭제한 요소의 앞 요소의 주소만 이어주면 된다(포인터의 값을 복사). 이는 얕은 복사라서 배열보다 삽입 삭제에 다는 비용이 적다는 말이다.
그런데 여기서 이러한 의문이 든다. 특정 값을 삭제하려면 임의 접근이 안되서 탐색을 해야하는데 그럼 결국 시간이 오래 걸리는 것이 아닌가? -> 배열과 trade off 라서 crud 기능 전부의 시간 복잡도는 비슷할 것 같다.
4. 비교해보기 ArrayList와 LinkedList
ArrayList와 LinkedList 비교
캐시 이점을 활용?
ArrayList와 LinkedList 성능 비교
여기서 아까 들었던 추측이 맞다는걸 확인할 수 있다. Linkedlist에서는 시간 복잡도가 search time + O(1) 이다. 그럼에도 불구하고 Arraylist보다 삽입삭제 기능이 좋을 수 밖에 없는 이유는 Arraylist가 O(n) 이기 때문인 것이었다.
두번째로 흥미로운 부분은 wasted space(average)가 같다는 점이다. 직관적으로는 왠지 Linkedlist가 wasted space 훨씬 적을 것 같은데 같다는 것이 신기하다.(나중에 알아보기로 하자)
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def search(self, target):
current = self.head
while current:
if current.data == target:
return True
current = current.next
return False
def delete(self, target):
if not self.head:
return
if self.head.data == target:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.data == target:
current.next = current.next.next
return
current = current.next
if __name__ == "__main__":
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
print("Linked List:")
linked_list.display()
target = 2
if linked_list.search(target):
print(f"{target}을(를) 찾았습니다.")
else:
print(f"{target}을(를) 찾지 못했습니다.")
target = 4
if linked_list.search(target):
print(f"{target}을(를) 찾았습니다.")
else:
print(f"{target}을(를) 찾지 못했습니다.")
linked_list.delete(2)
print("2 삭제 후:")
linked_list.display()
위 코드는 지피티가 파이썬으로 구현해준 간단한 의사코드이다. 삭제 부분을 보면 while 문으로 타겟 노드를 탐색하는 것을 볼 수 있다. 그렇다면 결국 삭제를 하는데에는 탐색하는데에 걸리는 시간이 걸린다.
- 연결리스트 삭제 알고리즘 내부 뜯어보기 (삭제하고 나서 이동시킬때 얕은 복사를 하는데 이 때 link field에 있는 다음 노드의 주소값을 그냥 넣는건지)
- Array List VS Linked List
