스택, 연결리스트 구현해보기

1학년때 c언어로 구현하면서 되게 어렵다고 생각했던 기억이 나네..

 

 

노드 클래스

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

        def __str__(self):
            return str(self.data)

        def __repr__(self):
            return str(self.data)

 

스택 클래스

class Stack:
    def __init__(self, mylist):
        self.head = Node(mylist[0])
        current = self.head
        for i in range(1, len(mylist)):
            if current.next == None:
                current.next = Node(mylist[i])
                current = current.next
        
    def __str__(self):
        mydata = ''
        current = self.head
        while current:
            mydata += ' ' + str(current.data)
            current = current.next
        return mydata.strip()

    def __repr__(self):
        mydata = ''
        current = self.head
        while current:
            mydata += ' ' + str(current.data)
            current = current.next
        return mydata.strip()

    def pop(self):
        current = self.head
        while current.next.next:
            current = current.next
        popnode = current.next            
        current.next = None
        return popnode

    def append(self, new):
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(new)

 

메서드 하나씩 살펴보기

 

mylist라는 리스트를 인자로 받아서 일단 Node객체 head를 만들고 next로 리스트안에 숫자들을 연결 연결 연결 해주었다.

def __init__(self, mylist):
        self.head = Node(mylist[0])
        current = self.head
        for i in range(1, len(mylist)):
            if current.next == None:
                current.next = Node(mylist[i])
                current = current.next

 

Stack 객체 print할때 갖고있는 data들을 보여주도록.

def __str__(self):
    mydata = ''
    current = self.head
    while current:
        mydata += ' ' + str(current.data)
        current = current.next
    return mydata.strip()

def __repr__(self):
    mydata = ''
    current = self.head
    while current:
        mydata += ' ' + str(current.data)
        current = current.next
    return mydata.strip()

 

스택의 pop은 제일 마지막 요소를 꺼내서 반환.

마지막 요소를 popnode로 하고 current.next = None으로 연결을 끊고 반환.

def pop(self):
    current = self.head
    while current.next.next:
        current = current.next
    popnode = current.next            
    current.next = None
    return popnode

 

append는 마지막에 요소를 추가.

마지막 요소의 next에 새로운 Node객체를 연결한다.

def append(self, new):
    current = self.head
    while current.next:
        current = current.next
    current.next = Node(new)

 

사용은 이렇게

myStack = Stack([1, 2, 3, 4, 5])
print(myStack.pop()) # 5
myStack.append(6)
print(myStack) # 1 2 3 4 6

---

연결 리스트 구현 심화?

 

iter 하고 next 주의하기.

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

class LinkedList:
    def __init__(self):
        init = Node('init')
        self.head = init
        self.tail = init
        self.count = 0

    def __len__(self):
        return self.count

    def __getitem__(self, index):
        current = self.head.next
        for _ in range(index):
            current = current.next
        return current.data

    def __str__(self):
        current = self.head.next
        result = ''
        for _ in range(self.count):
            result += f'{str(current.data)}, '
            current = current.next
        return f'<{result[:-2]}>'

    def __repr__(self):
        current = self.head.next
        result = ''
        for _ in range(self.count):
            result += f'{str(current.data)}, '
            current = current.next
        return f'<{result[:-2]}>'

    def __iter__(self):
        self.current = self.head.next
        return self

    def __next__(self):
        if self.current:
            data = self.current.data
            self.current = self.current.next
            return data
        else:
            raise StopIteration

    def append(self, data):
        new_node = Node(data)
        self.count += 1
        self.tail.next = new_node
        self.tail = new_node

    def pop(self):
        if self.count == 0:
            raise IndexError('pop from empty list')
        last_node_data = self.tail.data
        current = self.head.next
        for _ in range(self.count):
            if current.next is self.tail:
                self.tail = current
                break
            current = current.next
        self.count -= 1
        return last_node_data

    def find(self, data):
        if self.count == 0:
            return -1
        current = self.head.next
        for i in range(self.count):
            if current.data == data:
                return i
            current = current.next
        return -1

    def insert(self, index, data):
        current = self.head
        for _ in range(index):
            current = current.next
        new_node = Node(data)
        new_node.next = current.next
        current.next = new_node
        self.count += 1