Linked list (python으로 구현 해보기)

• 자료구조/알고리즘 강의 1주차

연결리스트란? 

각 원소(node)의 head에는 data를 저장하고, next에는 원소가 연결되어 있다면 다음 원소의 head 주소를 저장하여 접근 할 수 있게한 일종의 비엔나 소시지 같은 느낌이라고 보면 되겠다.

 

 

 [출처-파이썬알고리즘 인터뷰]

 

 

 

 

 

 

 

# 노드 선언
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# 리스트 선언
class L_List:
    def __init__(self):
        self.head = None
        self.length = 0

 이런식으로 node=[val][next] 꼴로 구현해 주었고, next = None인 이유는 연결하지 않은 노드 상태이기 때문.

 

만약 node를 n개 생성하여 node1 뒤로 node2를 연결시킨다면 node1.next = node2.head ... 인 형식이 될것이고, node1 앞으로 node2를 연결 시킨다면 node2.next=node1.head ... 이런식으로 나오게 함수를 정의하면 된다.

# 노드가 없을경우에 예외처리
    def isempty(self):
        return not bool(self.head)

	# 가장 앞의 노드에 삽입
    def add_front(self, val):
        node = Node(val)
        if not self.isempty():
            node.next = self.head
            self.head = node
        else:       #첫 node일경우 들어감.
            self.head = node
        self.length += 1

    # 가장 뒤의 노드에 삽입
    def add_end(self, val):
        if not self.isempty():
            node = self.head
            while node.next:
                node = node.next
            node.next = (Node(val))
        else: 
            self.head = Node(val)
        self.length += 1

 

 

마지막으로 직접 node value를 확인해 보는 함수를 정의해서 테스트까지 해보았다.

    def printnode(self):
        if not self.isempty():
            node = self.head
            while node:
                print(node.val, end=' ')
                node = node.next
            print()
        else:
            print('list is empty')
            
 if __name__ == '__main__':
    list = L_List()
    list2 = L_List()

    list.add_front(1)
    list.add_end(2)
    list.add_end(4)
    list.printnode()

    list2.add_front(1)
    list2.add_end(3)
    list2.add_end(4)
    list2.printnode()

결과

 

reference)

https://koosco.tistory.com/80