[자료구조]기본3_링크드리스트

 

 

LinkedList(연결리스트)

특징

노드객체 : data-next로 구성

헤드노드만 있으면 나머지는 순서있게 구성가능(실제로 메모리에는 여기저기 흩어있다)

동적배열보다 복잡하다(하지만 배열의 단점을 보완할 수 있다)

 

장점

• 개별적으로 위치하고 있는 원소의 주소를 연결하여, 하나의 자료구조를 이룬다
• 링크를 통해 원소에 접근하므로, 물리적인 순서를 맞추기위한 작업이 필요없다.
• 배열과 달리 크기가 정해진게 아니고, 동적으로 조정할 수 있기때문에 메모리의 효율적사용이 가능하다. 

 

 

 

노드객체만들기

1. 클래스만들기(노드를 만드는 틀)

2. 노드연결

 class Node:
 	"""링크드 리스트 노드 클래스"""
    
    def __init__(self, data);
    	self.data = data   # 노드가 저장할 데이터
        self.next = none   # 다음 노드에 대한 레버런스
 
 # 데이터 2, 3, 5, 7, 11을 담는 노드생성
 head_node = Node(2)
 node_1 = Node(3)
 node_2 = Node(5)
 node_3 = Node(7)
 tail_node = Node(11)
 
 # 노드연결
 head_node.next = node_1
 node_1.next = node_2
 node_2.next = node_3
 node_3.next = tail_node
 
 # 노드출력
 iterator = head_node
 
 while iterator is not None:
 	print(iterator.data)
    iterator = iterator.next
 
 

LinkedList 추가연산

class LinkedList:
	"""링크드 리스트 클래스"""
    
    def __init__(self):
    	self.data = None
        self.next = None
        
    def append(self, data):
    	"""링크드리스트 추가연산 메소드"""
        new_Node = Node(data)
        
        if self.head = None:       #링크드 리스트가 비어있는경우
           self.head = new_Node
           self.tail = new_Node
        else:					   # 링크드리스트가 비어있지않은경우
           self.tail.next = new_Node
           self.tail = new_node
            
            
#새로운 링크드 리스트 생성
my_list = LinkedList()

#링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)

#링크드 리스트 출력
iterator = my_list.head

while iterator is not None:
    print(iterator.data)
    iterator = iterator.next

        	

 

 

LinkedList에 접근 O(n)

인덱스가 저장된 주소로 접근했던 배열과 달리,

LinkedList는 레퍼런스를 통해 순서를 저장하기때문에 한번에 원하는 위치의 데이터에 접근불가

ex)인덱스 x에 있는 노드에 접근하려면 head에서 다음노드로 x번 가야함(접근메서드사용)

파라미터 : index

class LinkedList:

	def find_node_at(self, index):
    	iterator = self.head
        
        for _ in range(index):
        	iterator = iterator.next
            
        return iterator
        
# 접근
print(my_list.find_node_at(3).data)

   

LinkedList 탐색(선형탐색) O(n)

is not None : "끝까지 돈다"

def find_node_with_data(self, data):
	iterator = self.head
    
    while iterator is not None:
    	if iterator.data == data:
        	return iterator
            
        iterator = iterator.next
        
    return None

 

LinkedList에 삽입 O(1)

맨 끝에 삽입되는경우와, 중간에 삽입되는경우를 나누어서 접근

파라미터 : previous Node, data

def insert_after(self, previous_node, data):
  """주어진 노드 뒤 삽입연산 메소드"""
  new_node = Node(data)
  
  #가장 마지막 순서 삽입
  if previous_node is self.tail:
  	self.tail.next = new_node
    self.tail = new_node
  else: # 두 노드 사이에 삽입
  	new_node.next = previous_node.next
    previous_node.next = new_node

 

LinkedList에 삭제 O(1)

노드를 못찾게하는것을 삭제의 개념으로 생각(연결고리를 끊어서 못찾게해야함) 

직접삭제가 아닌, 관계를 나타내는 코드에서 빼준다

파라미터 : previous Node

 

📌지우려는 노드가 tail노드일때

if previous_node.next is self.tail:
	previous_node.next = None
    self.tail = previous_node

📌지우려는 노드가 tail노드가 아닐때

else:
	previous_node.next = previous_node.next.next

 

 

 

 

 

DoublyLinkedList(이중연결리스트)

DoublyLinkedList에 삽입 O(1)

def insert_after(self, previous_node, data):
	new_node = Node(data)
    
    #tail노드 다음에 삽입할때
    if previous_node is self.tail:
    	self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node
        
    else:      
    	#새node기준으로 정리
    	new_node.prev = prev_node
        new_node.next = prev_node.next
        
        #원래있던 node기준으로 정리
        prev_node.next.prev = new_node
        prev_node.next = new_node

더블리링크드리스트에 첫번째에 삽입하는경우

class LinkedList:
    """링크드 리스트 클래스"""
    def __init__(self):
            self.head = None  # 링크드 리스트 가장 앞 노드
            self.tail = None  # 링크드 리스 가장 뒤 노드

    def prepend(self, data):
        """링크드 리스트 가장 앞에 데이터를 추가시켜주는 메소드"""
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

 

 

DoublyLinkedList 삭제 O(1)

 

 def delete(self, node_to_delete):
        """더블리 링크드 리스트 삭제 연산 메소드"""
    
        # 링크드 리스트에서 마지막 남은 데이터를 삭제할 때
        if node_to_delete is self.head and node_to_delete is self.tail:
            self.tail = None
            self.head = None
    
        # 링크드 리스트 가장 앞 데이터 삭제할 때
        elif node_to_delete is self.head:
            self.head = self.head.next
            self.head.prev = None
    
        # 링크드 리스트 가장 뒤 데이터 삭제할 떄
        elif node_to_delete is self.tail:
            self.tail = self.tail.prev
            self.tail.next = None
    
        # 두 노드 사이에 있는 데이터 삭제할 때
        else:
            node_to_delete.prev.next = node_to_delete.next
            node_to_delete.next.prev = node_to_delete.prev
    
        # 삭제하는 노드 데이터 리턴
        return node_to_delete.data