배열의 단점을 극복한 것이 링크드 리스트이다.
링크드리스트는 배열과 달리 공간과 함께 뒤에 나올 데이터의 공간을 가르키는 주소값 공간과 함께 하나의 데이터로 관리한다.
연결 정보를 찾는 시간이 필요하므로 접근 속도가 느려진다.
중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요하다.
class Node:
def _init(self, data):
self.data = data
self.next = None
class Node (self,data, next.data = None):
self.data = data
self.next = next
node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1 // 가장앞에 있는주소이다.
class Node:
def _init_(self,data, next=None):
self.data = data
self.next = next
def add(data)
node = head
while nodex.next:
node = node.next
node3 = Node(1.5)
node = head
search = True
while node.next:
if node.data ==1;
search = False
else:
node = node.next
node_next = node.next
node.next = node3
node3.next = node_next
Class _init_(self, data, ndex=None):
self.data = data
self.next = next
Class NodeMgmt:
def _init_(self, data):
self.head = Node(data)
def add(self, data):
if self.haed == '':
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
기존의 링크드 리스트와 다르게 이전데이터의 주소도 저장하고 있다.
인덱스를 양방향에서 탐색할 수 있다.
이전 노드를 지정하기 위한 변수를 하나 더 사용하기 때문에 메모리를 더 많이 사용한다.
Class Node:
def _init_(self, data, prev = None, next=None):
self.prev = prev
self.data = data
self.next = next
Class NodeMamt:
def _init_(self, data):
self.head = Node(data)
self.tail = self.head
def insert(self, data):
if self.head = None:
self.haed = Node(data)
self.tail = self.haed
else:
node = self.haed
while node.next:
new = Node(data)
node.next = new
new.prev = node
node.tail = new
def desc(self):
node = sefl.head
prinf(node.data)
node = node.next
def search_from_head(self.data):
if sefl.head == none:
return False
node = sefl.head
while node:
if node.data == data:
return node
else:
node = node.next
=return False
def search_from_tail(self,data):
if self.tail = none:
return False
node = self.tail
while node:
if node.data == data:
return node
else:
node = node.prev
return False
def insert_before (self, data, before_data):
if self.head = None:
self.head = Node(data)
return True
else:
node = self.tail
while node.data != before_data:
node = node.prev
if node = None:
return False
new = Node(data)
before_new = node.prev
before_new.next = new
new.prev = before_new
new.next = node
node.prev = new