[프로그래머스 알고리즘] 7강, 8강, 9강: 연결 리스트 (Linked Lists)

연결 리스트 (Linked list)

• node에는 data와 next node의 link를 담고 있다.
• 노드 내의 데이터는 다른 구조로 이뤄져 있을 수 있음
• 리스트의 맨 앞, 리스트의 맨 끝, 노드의 개수를 기록해두면 좋다.

class Node:
	def __init__(self):
		self.data = data
		self.next = None

 

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

 

연산 정의

• 특정 원소 참조 (k번째)

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

• 리스트 순회 

과제 7로 구현되어 있다.

• 길이 얻어내기

self.nodeCount를 통해 길이를 알아낼 수 있다.

• 원소 삽입

삽입 위치	맨 앞	중간	맨 뒤
시간 복잡도	O(1)	O(n)	O(1)

 

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

• 원소 삭제

삭제 위치	맨 앞	중간	맨 뒤
특이 사항	head = curr.next	prev.next = curr.next	tail = prev prev.next = None
시간복잡도	O(n)	O(n)	O(n)

만약 list의 개수가 1개인데 원소를 삭제한다면? --> 과제 8로 구현되어 있다.

• 두 리스트 합치기

def concat(self, List)

연결할 리스트가 빈 리스트라면 self 반환

 

배열 vs 연결리스트

	배열	연결리스트
저장공간	연속된 위치	임의의 위치
특정원소 지칭	매우 간편, O(1)	선형탐색과 유사, O(n)

 

Dummy node가 추가된 linked list

연결리스트는 삽입과 삭제가 빠르고 유연하다는 것이 최대 장점이다. 하지만 우리의 현재 코드는 빠른 삽입, 삭제가 느리다. 

따라서, 맨 앞에 dummy node를 추가하여 삽입, 삭제를 편하게 함.

• 새로운 매서드 생성 

insertAfter(prev, newNode)
popAfter(prev)

• class LinkedList에 self.head = Node(None)으로 수정.

 

이 방법의 단점은 역방향으로 순회를 못한다는 점이다. 이 다음 강의에서는 양방향 연결 리스트를 배워볼 것이다.

 

 

---

7강, 8강 과제: 연결 리스트 순회와 노드 삭제

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 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 self.nodeCount == 1:
            curr = self.head
            self.head = None
            self.tail = None
            
        else:
            curr = self.getAt(pos)
            if pos == 1:
                self.head = curr.next
            elif pos == self.nodeCount:
                prev = self.getAt(pos - 1)
                self.tail = prev
                prev.next = None
            else:
                prev = self.getAt(pos -1)
                prev.next = curr.next
                
        self.nodeCount -= 1
        return curr.data
        


    def traverse(self):
        list = []
        if self.nodeCount == 0:
            pass
        else:
            for idx in range(1,self.nodeCount+1):
                list.append(self.getAt(idx).data)
        return list

 

9강 과제: dummy head를 가지는 연결 리스트 노드 삭제

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):
        curr = prev.next
        if curr == None:
            return None
        
        if curr.next == None:
            self.tail = prev
        
        prev.next = curr.next    
        self.nodeCount -= 1
        return curr.data


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

        prev = self.getAt(pos-1)
        return self.popAfter(prev)