6. Linked List(연결된 구조) 문제풀이

6.3 n개의 자료로 구성된 리스트를 단순 연결 구조로 표현하고자 한다. 다음 중 시간 복잡도가 가장 낮은 연산은?

 

1. 리스트의 길이 출력 -> O(n)
2. 어떤 노드의 다음 노드를 리스트에서 삭제-> O(1)
    -> 노드가 주어지므로 다음 노드를 리스트에서 삭제하는건 주어진 노드의 self.next를 삭제하고 다음 노드와 연결시켜주면 된다.
    -> 그렇기 때문에 O(1)

3. 어떤 노드의 바로 앞에 새로운 노드를 추가 -> O(n)

4. 마지막 노드의 데이터를 출력 -> O(n)

 

6.9 다음은 연결 리스트를 역순으로 변환하는 함수이다. 빈칸에 들어가야 하는 코드를 적으시오.

def reverse(head):
    p = head
    q = None
    while p != None:
        r = q
        q = p
        p = p.link
        q.link = r  # 답 위치
        self.head = q # 원래는 이 코드도 추가가 되어야 하지만.?
    return q

6.10 연결 리스트에서 어떤 노드를 삭제하려고 한다. 만약 삭제할 노드를 알고 있다면 삭제 연산의 시간 복잡도는 어떻게 되는가? 리스트를 단순 연결 구조로 구현한 경우와 이중 연결 구조로 구현한 경우에 대해 각각 시간 복잡도와 이유를 설명하라

 

1. 단순연결리스트 -> O(n)
    -> 단순연결리스트는 삭제할 노드의 prev 노드를 찾아야하기 때문에 O(n)의 시간이 소요되고

2. 이중연결리스트 -> O(1)  
    -> 이중연결리스트는 prev노드를 바로 찾을 수 있으니까 O(1)

 

6.11 연결된 큐를 원형 연결 구조로 구현할 때 큐 클래스의 데이터 멤버로 head가 아니라 tail을 사용하는 이유를 설명하라

-> 노드가 단순연결노드이기 때문에 tail에서 head로 가는건 O(1)의 시간복잡도로 가능하지만

-> head에서 tail로 가는건 O(n)의 시간이 걸리기 때문

6.12 연결 리스트 클래스 LinkedList에 모든 요소를 순서대로 화면에 출력하는 printForward()연산을 추가하라

def printForward(self):
    p = self.head
    while p != None:
        print(p.data)
        p = p.next

6.13 연결 리스트 클래스 LinkedList에 모든 요소를 역순으로 화면에 출력하는 printReverse()연산을 추가하라. 단, 순환을 이용해야 한다.

    def printReverse(self, node):
        p = node
        if p.next != None:
            self.printReverse(p.next)
            print(p.data)
        else:
            print(p.data)

6.14 연결 리스트 클래스 LinkedList에 리스트의 맨 끝에 새로운 요소를 추가하는 append() 연산을 추가하라.

def append(self, node):
        p = self.head
        while p.next != None:
            p = p.next
        p.next = node

6.15 연결 리스트 클래스 LinkedList에 2개의 리스트를 합치는 merge()연산을 구현하라. 연산 결과 리스트 A의 길이는 늘어나고, B의 길이는 0이 되도록 하라.

def merge(self, B):
        Apointer = self.head
        Bpointer = B.head
        #현재 리스트의 맨 끝으로 감
        while Apointer.next != None:
            Apointer = Apointer.next
        #B포인터의 값들을 하나하나 이어붙임            
        while Bpointer != None:
            self.append(ListNode(Bpointer.data, Apointer.next))
            Bpointer = Bpointer.next
            Apointer = Apointer.next

6.16 회문이란 앞뒤 어느 쪽에서 읽어도 같은 말, 구, 문 등을 의미한다. 예를 들면 "eye", "madam", "radar" 등이다. 구두점, 스페이스, 대소문자 등은 무시하고, 스택을 활용하여 주어진 문자열이 회문인지 아닌지를 결정하는 프로그램을 작성하라.

from LinkedStack import LinkedStack
from LinkedStack import ListNode

def checkPaindrome(word, stack):
    S = stack
    for i in range(0, len(word)):
        S.push(word[i])

    index = 0
    while S.isEmpty() != True: 
        pop = S.pop()
        if pop != word[index]:
            return print("회문아님")
        index += 1

    return print("회문임")



if __name__ == "__main__":
    x = input("단어를 입력하세요 :")
    S = LinkedStack()
    checkPaindrome(x, S)

6.17 단순연결 리스트를 이용한 연결된 큐 클래스를 구현하라. 데이터 멤버로는 전단을 가리키는 front와 후단을 가리키는 rear를 사용한다. 삽입은 후단을 통해, 삭제는 전단을 통해 이루어지도록 하라.

1. 삽입 : rear.next = InputNode

2. 삭제 : a = self.front // self.front = self.front.next // a.next = None

 

6.18 연결 리스트 클래스 LinkedList를 이중 연결 구조로 다시 구현하라.

 

1. 삽입 : beforeNode = 해당 위치-1, Node.next = beforeNode.next
nextNode = beforeNode.next, Node.before = nextNode.before
beforeNode.next = Node
nextNode.before = Node

2. 삭제 : deleteNode = 해당Node
		beforeNode = deleteNode.before
		nextNode = deleteNode.next
        
		beforeNode.next = deleteNode.next
		nextNode.before = deleteNode.before

 

 

6.19 문제는 너무 길어져서 다음에