[Python3 코딩테스트 (2)] Linked List

Linked List (with Node)

Linked List는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조

Node는 데이터 값과 next node의 주소값을 저장한다. Linked List는 메모리상에서 비연속적으로 저장이 되어 있지만, 각각의 node가 next node의 메모리 주소값을 가리킴으로써 논리적인 연속성을 갖게 된다.

물리적 비연속성, 논리적 연속성

각 node들은 데이터와 next node의 주소 정보를 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결될 수 있다. Array의 경우 연속성을 유지하기 위해 메모리상에서 순차적으로 데이터를 저장하는 방식을 사용하였지만, Linked List에는 메모리상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 조금 더 자유롭다. 다만 next node의 address도 추가적으로 저장해야 하기 때문에 데이터 하나 당 차지하는 메모리가 더 커진다.

Linked List의 다양한 활용

1. Linked List 자유자재로 구현(선형 자료구조 + 중간에 데이터 추가/삭제 용이)
   1. 데이터를 중간에 추가하거나 삭제할 때 특히 요긴하게 사용된다.
2. Tree or Graph에 활용

class Node : 
	def __init__(self, value = 0, next = Node):
		self.value = value
		self.next = next

class LinkedList(object):
	def __init__(self):
		self.head = None
	def append(self, value):
		new_node = Node(value)
		if self.head is NoneL
			self.head = new_node
		else:
			current = self.head
			while(current.next):
				current = current.next
			current.next = new_node
		

2095. Delete the Middle Node of a Linked List

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/

Delete the Middle Node of a Linked List - LeetCode

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 우선 [n/2]까지 간다 -> 정적 배열과 달리 LinkedList에서 해당 노드에 어떻게 도달할 것인가
        # *중요* 속도차이가 2배 나는 두 개의 노드를 활용 
        # -> 한 노드가 끝에 도달했을 때 다른 하나는 중간에 도달 
        if head.next == None:
            return None
        
        slow = head
        fast = head.next.next
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
    
        # 삭제될 노드의 전 노트를 다음 노드에 연결
        slow.next = slow.next.next
        # [n/2] 노드 삭제 -> python의 경우 garbage collector에 의해 자동 삭제됨
        # 출력 
        return head

중간 노드를 삭제하기 위해 중간 노드까지 어떻게 도달할 지 아이디어를 내는 것이 중요했던 문제

2배 속도 차이 나는 노드를 활용하여, 한 노드가 LinkedList의 끝에 도달했을 때, 다른 한 노드는 중간에 도달하게 한다.

---

328. Odd Even Linked List

https://leetcode.com/problems/odd-even-linked-list/description/

Odd Even Linked List - LeetCode

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        #LinkedList가 연결을 2개 씩도 할 수 있으려나?흠.. 안될 것같은데..
        #짝수번째 있는 노드들 중에 뒤에서부터 연결을 시작한다.
        #근데 연결을 시키다가...  끊어지지 않을까..?
        #모범답안을 봤더니 dummy를 만들어서 연결시킨다.
        #아 근데 문제에 제약 조건: O(1) extra space이기 pointer를 활용해야 함
        
        if not head: return head

        odd = head
        evenHead = even = head.next
        
        while(even and even.next):
            # Connect the current odd node to the next odd node
            odd.next = odd.next.next
            # Move the current odd node to the next odd node
            odd = odd.next
            even.next = even.next.next
            even = even.next

        # Connect the last odd node to the start of the even node
        odd.next = evenHead

        return head

 

 

 

 

 

 

https://inf.run/3hPE

코딩테스트 [ ALL IN ONE ] - 인프런 | 강의

위의 강의를 수강하고, 공부할 때 참고하기 위해 정리한 내용입니다.