[자료구조] 이중 링크드 리스트 (Double Linked List)

더블 링크드 리스트 기본 구조

  - 이중 링크드 리스트라고도 한다.

  - 장점

      • 양방향으로 연결 노드 탐색이 양쪽으로 모두 가능하다.

      • 링크드 리스트의 항상 앞에서부터 검색해야 되는 단점을 보완

 

이중 링크드 리스트 기본 구조

  - 노드는 앞뒤로 주소를 가지고 있으므로 앞에서부터 검색할지 뒤에서 부터 검색할지 판단해서

    검색 속도를 빠르게 할 수 있다.

 

이중 링크드 리스트 구현

class Node:								# 노드 생성
	def __init__(self, data):
		self.prev = None
        self.data = data
        self.next = None

class NodeMgmt:
	def __init__(self, data):
		self.head = Node(data)
		self.tail = self.head
        
	def insert(self, data):				# 노드 추가
		if self.head == None:
			self.head = Node(data)
			self.tail = self.head
		else:
			node = self.head
			while node.next:			# while문이 계속 반복이 된다면 주소가 계속 존재함
				node = node.next		# 작업을 하는 이유는 노드의 끝을 찾기 위해
			new = Node(data)
			node.next = new
			new.prev = node
			self.tail = new
            
	def desc(self):
		node = self.head
		while node:
			print(node.data)
			node = node.next
            
	def search_from_head(self, data):	# 앞에서부터 검색
		if self.head == None:
			return False

		node = self.head
		while node:
			if node.data == data:
				return node
			else:
				node = node.prev
		return False
        
	def search_from_tail(self, data):	# 뒤에서부터 검색
		if self.head == 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):		# 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
			return True
            
	def insert_after(self, data, after_data):		# after_data 값 뒤에 데이터 생성
		if self.head == None:
			self.head = Node(data)
			return True
		else:
			node = self.head
			while node.data != after_data:
				node = node.next
				if node == None:
					return False
			new  = Node(data)
			after_new = node.next
			new.next = after_new
			new.prev = node
			node.next = new
			if new.next == None:
				self.tail = new
			return True