2. 연결 리스트 (Linked List)

1. 노드 정의

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

노드는 자신이 가지고 있는 값을 나타내는 data 와

다음 노드를 가리키는 next 를 가지고 있다.

 

2. 연결 리스트 생성자

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

 

3. 연결리스트 인덱스에 해당하는 노드를 가져오는 메서드 - getAt

def getAt(self, pos):
    # 입력한 인덱스가 범위를 벗어나는 경우
    if pos < 1 or pos > self.nodeCount:
        return IndexError
    i = 1
    #처음부터
    curr = self.head
    
    #입력한 인덱스까지 curr 를 변화함
    while i < pos:
       curr = curr.next
       i += 1
    return curr

 

4. 연길리스트 순회하는 메서드 - traverse

def traverse(self):
    result = []
    curr = self.head
    #tail.next 가 None 이라 None이 될 때까지 반복
    while curr != None:
        result.append(curr.data)
        curr = curr.next
    return result

 

5. 인덱스 위치의 노드를 삽입하는 메서드 - insertAt

def insertAt(self, pos, newNode):
    #인덱스가 범위를 벗어나는 경우 ( 맨 뒤에 삽입하는 경우가 있기 때문에 "+1" 까지 허용함)
    if pos < 1 or pos > self.nodeCount + 1:
        return IndexError
    
    #맨 앞에 삽입
    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 를 사용 )

 - 삽입하려는 위치가 리스트 맨 끝일 때 ( tail 을 사용 )

     tail 을 이용하면 처음부터 순회할 필요없이 맨 뒤에 삽입할 수 있다. ( 특별하게 취급 )  O(n) -> O(1)

 

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

맨 앞에 삽입하는 경우 : O(1)

중간에 삽입하는 경우 : O(n)

맨 끝에 삽입하는 경우 : O(1)

---

6. 인덱스 위치의 노드를 삭제하는 메서드 - popAt

    def popAt(self, pos):
        # 삭제할때는 nodeCount 보다 큰 index가 없기 때문에 "+1" 을 제외
        if pos < 1 or pos > self.nodeCount:
            return IndexError
        
        # prev 와 curr 정의
        prev = self.getAt(pos - 1)
        curr = self.getAt(pos)
        
        # 마지막 한개의 노드를 삭제하는 경우
        if self.nodeCount == 1:
            self.head = None
            self.tail = None
        else :
            #맨 앞의 노드를 삭제하는 경우
            if pos == 1:
                self.head = curr.next
            #맨 뒤의 노드를 삭제하는 경우
            elif pos == self.nodeCount:
                self.tail = prev
                prev.next = None
            # 중간의 있는 노드를 삭제하는 경우
            else : 
                prev.next = curr.next
        self.nodeCount -= 1
        return curr.data

 

고려사항 : 

 - 입력한 인덱스가 범위에서 벗어나는 경우 예외 처리

 - 삭제하려는 노드가 맨 앞의 것일 때 ( head 조정 필요 )

 - 맨 끝의 노드를 삭제할 때 ( tail 조정 필요)

     * tail 로 맨 끝의 노드를 삭제할 수 없다. tail은 prev를 알 수 가 없다. O(n)

 - 마지막 노드를 삭제할 때

 

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

맨 앞에 삽입하는 경우 : O(1)

중간에 삽입하는 경우 : O(n)

맨 끝에 삽입하는 경우 : O(n)

 

---

7. 두 리스트의 연결 - concat

def concat(self, L):
    self.tail.next = L.head
    # 뒤의 붙이려고 하는 리스트가 비어있는 경우 예외처리
    if L.tail:
        self.tail = L.tail
    self.nodeCount += L.nodeCount
    

연결 리스트는 기존 리스트의 비해 해당 인덱스로 찾아갈때 O(n) 의 시간이 걸린다. ( 무조건 처음부터.. )

하지만 삽입과 삭제가 빠르다는 장점이 있어 사용되고 있다.

 

여기 까지 연결 리스트 기본에 대해서 알아보았다.

다음에는 dummy head 를 포함시켜 연결리스트를 더 간결하게 구현해보는 방법을 알아보자.