지난번에 연결리스트의 getAt 메소드까지 구현을 해보았다. 이번에는 더 다양한 연산을 구현해보려고 한다!

연결 리스트(Linked List) (2)

연결 리스트 연산

1. 특정 원소 참조 (k번째)
2. 리스트 순회
3. 길이 얻어내기
4. 원소 삽입
5. 원소 삭제
6. 두 리스트 합치기

원소의 삽입

def insertAt(self, pos, newNode):

• pos가 가리키는 위치에
• newNode를 삽입하고 성공/실패에 따라 True/False를 리턴
  (이때, pos의 범위: 1 <= pos <= nodeCount + 1)
• L.insertAt(pos, newNode)
• pos-1과 pos사이에 newNode를 삽입. pos - 1번째의 node를 prev라고 한다.

insertAt 구현
1. newNode의 뒤쪽 노드 조정: prev.next(pos번째 노드)를 newNode가 가리키도록 조정한다.
2. 앞선(prev) 노드가 newNode를 가리키도록 한다. newNode를 prev.next가 가리키도록 조정한다.
3. nodeCount + 1
1번과 2번이 바뀌면 안된다.

def insertAt(self, pos, newNode):
	prev = self.getAt(pos-1)
    	newNode.next = prev.next
    	prev.next = newNode
    	self.nodeCount += 1

코드 구현 시 주의사항

(1) 삽입하려는 위치가 리스트 맨 앞일 때,

• prev가 없다.
• Head 조정 필요

(2) 삽입하려는 위치가 리스트 맨 끝일 때,

• Tail 조정 필요

(3) 빈 리스트에 삽입 시
-> 위 두조건에 의해 처리된다.

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:
    	prev = self.getAt(pos - 1_
        newNode.next = prev.next
        preve.next = newNode
    if pos == self.nodeCount + 1:
    	self.tail = newNode
    
    self.nodeCount += 1
    return True

추가 조정 사항

• 삽입하려는 위치가 리스트 맨 끝일 경우 즉, pos == nodeCount + 1 인 경우 굳이 getAt을 사용하지 않아도 된다.
• tail을 활용하면 되기 때문! 삽입 전 prev가 tail이다.
• tail에 nextlink를 newNode로 newNode의 next는 None으로
  즉, 맨 앞아서부터 찾아갈 필요가 없다.

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
        preve.next = newNode
    
    if pos == self.nodeCount + 1:
    	self.tail = newNode
    
    self.nodeCount += 1
    return True

최종 총 코드 (모든 메소드)

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 __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr is not None:
            s += repr(curr.data)
            if curr.next is not None:
                s += ' -> '
            curr = curr.next
        return s


    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 getLength(self):
        return self.nodeCount


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


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

a = Node(67)
b = Node(34)
c = Node(28)
L = LinkedList() # empty
L.insertAt(1, a)
L.insertAt(2, b)
L.insertAt(3, c)

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

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

원소의 삭제

def popAt(self, pos):

• pos가 가리키는 위치의
• node를 삭제하고
• 그 node의 데이터를 리턴 (r = L.popAt(pos))
  (이때, pos의 범위: 1<= pos <= nodeCount)
• pos -1 / pos / pos + 1
  • prev: pos -1번째 노드
  • curr: pos 번째 노드

popAt 구현
1. prev.next를 curr.next로 조정
2. curr의 값을 뽑아 return
3. nodeCount -= 1

코드 구현 주의사항
(1) 삭제하려는 node가 맨 앞의 것일 때,

• prev가 없다.
• head 조정 필요 (pos+1로)

(2) 리스트 맨 끝의 node를 삭제할 때,

• Tail 조정 필요 (pos-1로)

(3) 유일한 노드를 삭제할 때,

• 이 두 조건에 의해 처리되는가?

(4) 삭제하려는 node가 마지막 node일 때, 즉 pos == nodeCount인 경우

• tail 이용 불가능
• prev를 찾을 방법이 없으므로 앞에서부터 찾아야한다.

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

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

두 리스트의 연결

def concat(self, L):

• 연결 리스트 self의 뒤에 또 다른 연결 리스트인 L을 이어 붙임
• L1.concat(L2)
• L1 즉 self.tail의 next가 L2의 head를 가르키는 구조
• self.tail = L2.tail

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

코드 구현시 주의할 점

• 뒤에 이어붙이는 L가 비어있는 경우 tail을 옮기면 안됨

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