Python 자료구조

연결리스트 Linked List

Linked List는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조이다. Node는 데이터 값과 next node의 주소값을 저장한다. Linked List는 메모리상에서는 비연속적으로 저장이되어 있지만, 각각의 node가 next node의 메모리 주소값을 가리킴으로써 논리적인 연속성을 가지게 된다.

물리적 비연속적, 논리적 연속적

• 각 node들은 데이터를 저장할 뿐 아니라, ndext node의 address정보도 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결 될 수 있다.
• Array의 경우 연속성을 유지하기 위해 메모리 상에서 순차적으로 데이터를 저장하는 방식을 사용했지만, Linked List에는 메모리상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 자유롭다
• 반면 next node의 address도 추가적으로 저장하기 때문에 데이터 하나당 차지하는 메모리가 크다

Node 기초

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

# 노드 생성
first = Node(1)
second = Node(2)
third = Node(3)

# 노드 끼리 연결
first.next = second
second.next = third
first.value = 6

LinkedList Class 생성하기

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


def append(self, value):
    new_node = Node(value)
    if self.head is None:
        self.head = new_node
    else:
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node

    
def get(self, idx):
    current = self.head
    for i in range(idx):
        if current is None:
            raise IndexError("list index out of range")
        current = current.next
    return current.value
    
def insert(self, idx, value):
    new_node = Node(value)
    if idx == 0:
        new_node.next = self.head
        self.head = new_node
    else:
        current = self.head
        for i in range(idx - 1):
            if current is None:
                raise IndexError("list index out of range")
            current = current.next
        new_node.next = current.next
        current.next = new_node

def delete(self, idx):
    if idx == 0:
        self.head = self.head.next
    else:
        current = self.head
        for i in range(idx - 1):
            if current is None:
                raise IndexError("list index out of range")
            current = current.next
        if current.next is None:
            raise IndexError("list index out of range")
        current.next = current.next.next

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

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head
    
    def insert_before(self, data, before_data):
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.tail
            while node.data != before_data:
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.next = node
            return True

    def insert_after(self, data, after_data):
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.head
            while node.data != after_data:
                node = node.next
                if node == None:
                    return False
            new = Node(data)
            after_new = node.next
            new.next = after_new
            new.prev = node
            node.next = new
            if new.next == None:
                self.tail = new
            return True

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

LinkedList 코드에는 딱 정해진 정답이 없다.