4.리스트(연결 리스트)

1. Linked List

- 각각의 원소들은 자기 자신의 다음을 알고 있어서 삽입,삭제 시에 Big-O(1) 시간을 소모

- 원하는 위치에 삽입을 하려면 Search 과정이 생겨 Big-O(n) 시간을 소모, 삭제도 동일한 시간을 소모

- Search, 삽입, 삭제 에도 결국 Big-O(n) 시간을 소모 

1-1. Linked List ADT

- init(self, sort)

- 링크드 리스트 초기화 

- sort는 sort 함수 지정

- append(self, data)

- data값을 node에 전달하여 저장

- append_with_sort(self, data)

- data값을 오름 차순으로 정렬하며 저장

- remove(self, index):

- 지정한 인덱스의 데이터를 삭제한다.

- search(self, search_data)

- 현재 링크드 리스트에서 특정한 데이터를 찾는다

- 찾으면 결과값을 리턴, 찾지 못하면 False

- get(self, index)

- 지정한 인덱스의 값을 반환한다.

- pop(self)

- 가장 처음 값을 반환한다.

- display(self)

- 모든 값을 보여준다.

- count(self):

- 링크드 리스트에 저장되어 있는 데이터의 수를 반환한다.

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


class LinkedList:
    def __init__(self, sort=False):
        self.head = None
        self.tail = None
        self.total = 0
        self.sort = sort if sort else lambda x, y: x > y

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            self.total += 1
        else:
            self.tail.next = new_node
            self.tail = new_node
            self.total += 1

    def append_with_sort(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            self.total += 1
        else:
            prev = self.head
            if prev is self.head:
                if self.sort(prev.data, new_node.data):
                    new_node.next = prev
                    self.head = new_node
                    self.total += 1
                    return True
            while prev.next:
                current = prev.next
                if self.sort(current.data, new_node.data):
                    break
                prev = prev.next
            new_node.next = prev.next
            prev.next = new_node
            self.tail = new_node
            self.total += 1

    def search(self, data):
        node = self.head
        if node.data == data:
            return True
        while node.next:
            node = node.next
            if node.data == data:
                return True
        return False

    def get(self, index):
        node = self.head
        for i in range(index):
            if not node.next:
                return False
            node = node.next
        return node.data

    def pop(self):
        pop_data = self.head
        self.head = self.head.next
        self.total -= 1
        return pop_data.data

    def remove(self, index):
        if index >= self.count():
            return False
        node = self.head
        parent = None
        if index == 0:
            self.head = node.next
            self.total -= 1
        else:
            for i in range(index):
                child = node.next
                if not child.next:
                    node.next = None
                    return True
                parent = node
                node = node.next
            parent.next = node.next
            self.total -= 1
            return True
        return False

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

    def count(self):
        return self.total


L = LinkedList()
L.append_with_sort(2)
L.append_with_sort(1)
L.append_with_sort(8)
L.append_with_sort(4)
print(f'pop : {L.pop()}')
print(f'remove_data : {L.remove(4)}')
print(f'index 2 data : {L.get(2)}')
print(f'total : {L.count()}')
print(f'search data 2 : {L.search(2)}')
L.display()

---------------------------------------------------------------------
pop : 1
remove_data : False
index 2 data : 8
total : 3
search data 2 : True
2
4
8

2. Dummy Linked List

- head에 dummy노드를 두어서 코드를 간결화 하게 한다.

- dummy 노드는 아무 의미 없는 노드다. 하지만 linked list 직접 구현 해보면 그 필요성을 알게된다. 

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


class DummyLinkedList:
    def __init__(self, sort=False):
        dummy = Node('dummy')
        self.head = dummy
        self.tail = dummy
        self.total = 0
        self.sort = sort if sort else lambda x, y: x > y

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

    def append_with_sort(self, data):
        if self.total == 0:
            return self.append(data)
        new_node = Node(data)
        prev = self.head
        while prev.next:
            current = prev.next
            if self.sort(current.data, new_node.data):
                break
            prev = prev.next
        new_node.next = prev.next
        prev.next = new_node
        self.tail = new_node
        self.total += 1

    def search(self, data):
        node = self.head
        while node.next:
            node = node.next
            if node.data == data:
                return True
        return False

    def get(self, index):
        node = self.head.next
        for i in range(index):
            if not node.next:
                return False
            node = node.next
        return node.data

    def pop(self):
        pop_data = self.head.next
        self.head.next = pop_data.next
        self.total -= 1
        return pop_data.data

    def remove(self, index):
        if index >= self.count() or index < 0:
            return False
        node = self.head
        parent = None
        for i in range(index + 1):
            child = node.next
            if not child.next:
                node.next = None
                return True
            parent = node
            node = node.next
        parent.next = node.next
        self.total -= 1
        return True

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

    def count(self):
        return self.total