1. 연결 리스트(Linked Lists)


1-1. 추상적 자료구조(Abstract Data Structures)

  • Data
    • 정수, 문자열, 레코트, …
  • A set of operations
    • 삽입, 삭제, 순회, …
    • 정렬, 탐색, …



1-2. 연결 리스트(Linked Lists) 구현

연산정의

  1. 특정 원소 참조(k번째)
  2. 리스트 순회
  3. 길이 얻어내기
  4. 원소 삽입 코드 구현 주의사항
    • 삽입하려는 위치가 리스트 맨 앞일 때 * prev 없음
      • Head 조정 필요
    • 삽입하려는 위치가 리스트 맨 끝일 때 * Tail 조정 필요
    • 빈 리스트에 삽입할 때? * 이 두조건에 의해 처리됨
  5. 원소 삭제 코드 구현 주의사항pr
    • 삭제하려는 node가 맨앞의 것일 때 * prev 없음 * Head 조정 필요
    • 리스트 맨 끝의 node를 삭제할 때 * Tail 조정 필요
  6. 두 리스트 합치기
class Node:
    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    def traverse(self):
        cur = self.head
        clist = []
        while cur is not None:
            clist.append(cur.data)
            cur = cur.next
        return clist

    def insertAt(self, pos, newNode):
    	if pos < 1 or pos > self.nodeCount + 1:
        	return False

        if pos == 1:
        	newNode.next = self.head
            self.head = newNode

        else:
        	if pos == self.nodeCount + 1:
            	prev = self.tail
            else:
            	prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:
        	self.tail = newNode

        self.nodeCount += 1
        return True

	def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError

        if pos == 1:
            delete_node = self.head
            self.head = self.head.next
            return delete_node.data

        else:
            if pos == self.nodeCount:
                delete_node = self.tail
                self.tail = self.getAt(pos-1)
                self.tail.next = None

            else:
                delete_node = self.getAt(pos)
                prev = self.getAt(pos-1)
                prev.next = self.getAt(pos).next

            self.nodeCount -= 1
            return delete_node.data

    def contact(self, L):
        self.tail.next = L.head
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount

연결 리스트 원소 삽입의 복잡도

맨 앞에 삽입하는 경우: O(1) 중간에 삽입하는 경우: O(n) 맨 끝에 삽입하는 경우: O(1)

연결 리스트 원소 삭제의 복잡도

맨 앞에서 삭제하는 경우: O(1) 중간에 삭제하는 경우: O(n) 맨 끝에 삭제하는 경우: O(n)

연결 리스트가 힘을 발휘할 때

삽입과 삭제가 유연하다는 것이 가장 큰 장점



1-3. 연결 리스트 (dummy head)

연산정의

  1. 길이 얻어내기
  2. 리스트 순회
  3. 특정 우너소 참조(k번째)
  4. 원소 삽입
    • prev가 가리키는 node의 다음에 newNode를 삽입하고 성공/실패에 따라 True/False를 리턴
  5. 원소 삭제
    • def popAfter(self, prev):
      • prev의 다음 node를 삭제하고 그 node의 data를 리턴
    • 코드 구현 주의사항
      • prev가 마지막 node일 때(prev.next == None)
        • 삭제할 node 없음
        • return None
      • 리스트 맨끝의 node를 삭제할때 (curr.next == None)
        • Tail 조정 필요
  6. 두 리스트 합치기
class Node:

    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail


    def traverse(self):
        result = []
        curr = self.head
        while curr.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr


    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        if prev.next is None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        remove_node = prev.next
        if remove_node.next is None:
            self.tail = prev
        prev.next = remove_node.next
        self.nodeCount -= 1
        return remove_node.data

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        prev = self.getAt(pos - 1)
        
        return self.popAfter(prev)


def solution(x):
    return 0