링크드 리스트

정의

 노드라는 단위의 데이터를 저장하고 테이터가 저장된 각 노드들을 순서대로 연결시켜서 만든 자료 구조

 

노드(각각의 객체)

 1. 데이터 : 값, 정보

 2. next : 다음노드에 대한 레퍼런스

 ex) n_1 -> n_2

       n_1.next = n_2

 3. head : 링크드리스트의 첫번째 노드 객체

 

 링크드 리스트 [접근] 시간 복잡도

  1. 접근하고 싶은 인덱스가 x라면

      -> 인덱스 x에 있는 노드에 접근하려면 head에서 다음 노드로 x번 간다.

      -> 최악의 경우 맨마지막 데이터까지 접근해야한다. 즉, head에서 다음 노드로 n -1 번 움직인다.

      -> O(n)

  링크드 리스트 [탐색] 시간 복잡도

   1. 접근하고 싶은 인덱스가 x라면

       -> 최악의 경우 맨마지막 데이터까지 접근해야한다.

       -> O(n)

  링크드 리스트 삽입, 삭제 시간 복잡도

   1. 삭제할 인덱스의 주변 노드들에 연결된 레퍼런스만 수정

       -> O(1)

 

class Node:
	"""링크드리스트의 노드 클래스"""
    def __init__(self, data):
    	self.data = data # 노드가 저장하는 데이터
        self.next = None # 다음 노드에 대한 레퍼런스
        
class LinkedList:
	"""링크드 리스트 클래스"""
    
    def __init__(self):
    	self.head = None
        self.tail = None
    
    def delete_after(self, previous_node):
    	"""링크드 리스트 삭제연산. 주어진 노드 뒤 노드를 삭제한다"""
        data = previous_node.next.data
        
        # 지우려는 노드가 tail 노드일 때:
        if previous_node.next is self.tail:
        	previous_node.next = None
            self.tail = previous_node
        # 두 노드 사이 노드를 지울 때:
        else:
        	previous_node.next = previous_node.next.next
        
        return data
        
    def insert_after(self, previous_node, data):
    	"""링크드 리스트 주어진 노드 뒤 삽입 연산 메소드"""
        # 새로운 데이터를 저장하는 노드
        # 원래 있는 링크드 리스트에 연결
        new_node = Node(data)
        # tail 노드 다음에 노드를 삽입할 때
        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
        	
    def find_node_at(self, index):
    	"""링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정"""
        iterator = self.head
        
        for _ in range(index):
        	iterator = iterator.next
        # n번째 노드를 가르킬려면 n번 연산해야하므로
        return iterator
    
    
    def append(self, data):
    	"""링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)
        
        # 어차피 하나밖에 없으니까 head 이면서 tail이다.
        if self.head is None:
        	self.head = new_node
            self.tail = new_node
        else:
            # 현재 tail을 새로운 노드로
            # 추가된 노드가 tail 이므로 tail 설정
        	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)

print(my_list)

node_2 = my_list.find_node_at(2) # 인덱스 2 노드 접근
my_list.delete_after(node_2) # 인덱스 2 뒤 데이터 삭제

print(my_list)

second_to_last_node = my_list.find_node_at(2) # 맨 끄텡서 두 번째 노드 접근
print(my_list.delete_after(second_to_last_node)) # tail 노드 삭제

print(my_list)

# 링크드 리스트 노드에 접근 (데이터 가지고 오기)
# 인덱스 3의 노드의 .data에 접근
print(my_list.find_node_at(3).data)

# 링크드 리스트 노드에 접근 (데이터 바꾸기)
my_list.find_node_at(2).data = 13

print(my_list) # 전체 링크드 리스트 출력

node_2 = my_list.find_node_at(2) # 인덱스 2에 있는 노드 접근
my_list.insert_after(node_2, 6) # 인덱스 2 뒤에 6 삽입

print(my_list)

head_node = my_list.head # 헤드 노드 접근
my_list.insert_after(head_node, 9) # 헤드 노드 뒤에 9 삽입


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

while iterator is not None:
	print(iterator.data)
    iterator = iterator.next
        	
    
       
# 데이터 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_noe

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