자료구조 Linked List

lacblueeun·2020년 12월 18일
0

1. 링크드 리스트(Linked List)

배열의 단점을 극복한 것이 링크드 리스트이다.
링크드리스트는 배열과 달리 공간과 함께 뒤에 나올 데이터의 공간을 가르키는 주소값 공간과 함께 하나의 데이터로 관리한다.

1-2 단점

연결 정보를 찾는 시간이 필요하므로 접근 속도가 느려진다.
중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요하다.

1-3 링크드 리스트 구현

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        

1-4 링크드 리스트 데이터 사이에 데이터 추가

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

1-5 파이썬 객체지향 프로그래밍으로 링크드 리스트

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  	

2. 더블 링크드 리스트 (Double Linked List)

기존의 링크드 리스트와 다르게 이전데이터의 주소도 저장하고 있다.

2-1 장점

인덱스를 양방향에서 탐색할 수 있다.

2-2 단점

이전 노드를 지정하기 위한 변수를 하나 더 사용하기 때문에 메모리를 더 많이 사용한다.

2-3 더블 링크드 리스트 구현

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               
profile
Go for Frontend Developer 🧪

0개의 댓글