Linked Array

Node 구현

class Node:

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

Linked Array 구현

1. __init__ 생성자

class LinkedList:

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

2. traverse

• head부터 순회하면서 list에 추가
• print를 하면 이 결과값을 출력

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

def __str__(self):
    return self.traverse().__str__()

3. __getitem__

• 인덱싱 구현

def __getitem__(self, idx):
        
    if 0 <= idx < self.nodeCount:
        node = self.head.next
        for _ in range(idx):
            node = node.next
        return node
        
    else:
        raise IndexError

3. insertAfter

• 지정한 노드 앞의 노드 삽입

def insertAfter(self, prev, newNode):

    newNode.next = prev.next
    prev.next = newNode
    
    if newNode.next is None:
        self.tail = newNode
    
    self.nodeCount += 1

4. insertAt

• 지정한 위치에 노드 삽입

def insertAt(self, idx, newNode):
        
    if 0<= idx < self.nodeCount + 1:
            
        if idx == 0 :
            prev = self.head
        else:
            prev = self[idx-1]
            
        return self.insertAfter(prev, newNode)
                
    else:
        raise IndexError

5. popAfter

• 지정한 노드 앞에 노드 꺼내기

def popAfter(self, prev):
        
    curr = prev.next
    prev.next = curr.next
        
    if curr.next is None:
        self.tail = prev if prev is not self.head else None

    self.nodeCount -= 1
        
    return curr.data

6. popAt

• 지정한 위치의 노드 꺼내기

def popAt(self, idx):
        
    if 0 <= idx < self.nodeCount:
            
        if idx == 0 :
            prev = self.head
        else:
            prev = self[idx-1]
            
        return self.popAfter(prev)
                
    else:
        raise IndexError

7. concat

• 다른 linked list를 끝에 연결

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

소스코드 : LinkedList.py