1. 링크드 리스트란?
- 배열의 단점을 극복하기 위해 만들어짐
- 배열은 미리 메모리 사이즈를 할당하고 사용해야 함
- 메모리할당을 미리예약하지않고 필요할때마다 데이터를 추가추가할수 있는 구조
- 데이터 + next 데이터를 가르킬 주소를 하나의 데이터라고 보면 된다.
- 그런테 이것을 데이터라고 부를수 없어 데이터와 주소를 하나로 부르는 것을 노드라고 한다.
- 다음 데이터를 가르킬 주소라고 하기도 하지만 포인터라고 얘기한다.
링크드 리스트는 노드와 노드의 연결이다.
노드는 데이터와 다음 노드의 연결정보를 갖는 공간이다.
2. 링크드 리스트 구현
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | class Node: def __init__(self, data): self.data = data self.next = None class NodeMgmt: def __init__(self, data): self.head = Node(data) def add(self, data): if self.head == '': self.head = Node(data) else: node = self.head while node.next: node = node.next node.next = Node(data) def desc(self): node = self.head while node: print(node.data) node = node.next def delete(self, data): # 헤드값 없을때 if self.head == '': print("해당값을 가진 노드가 없습니다.") return # 지우는값이 헤드값일때 if self.head.data == data: tmp = self.head self.head = self.head.next del tmp else: # 지우는 값이 중간값일때 node = self.head while node.next: if node.next.data == data: temp = node.next node.next = node.next.next del temp return else: node = node.next linkedlist1 = NodeMgmt(0) # 0 linkedlist1.add(1) # 0 1 linkedlist1.add(2) # 0 1 2 linkedlist1.add(3) # 0 1 2 3 linkedlist1.desc() # 0 1 2 3 linkedlist1.delete(1) # 0 2 3 linkedlist1.desc() # 0 2 3 | cs |
링크드 리스트는 데이터가 계속 체이닝 되어서 찾아가는것인데
노드가 10000개 있고 찾으려는 데이터값이 9000번대에 있다면
맨 앞에서부터 링크드 되어있는 리스트의 값을 찾아가야 한다.
하지만 뒤에서부터 찾는다면 1000번만 찾으면 값을 찾을 수 있다.
prev, tail을 갖는 것이 더블 링크드 리스트이다.
더블링크드 리스트는 추후에 정리할 예정이다.