2주차_링크드 리스트 구현

 

링크드 리스트 자료구조 구현방법!

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

node = Node(3)
first_node = Node(4)
node.next = first_node
"""
node #[3]
node.next #[4]
node.next.data #4
"""
print(node.next.data) #4
print(node.data) #3

클래스의 생성자에 data를 인자로 받아서 self.data에 저장하고

현재는 다음 이어진 노드가 없기 대문에 self.next에는 None을 넣어둔다.

 

그리고 노드를 만들어서 연결을 해준다.

 

노드가 많다면 저 코드를 그만큼 쳐줘야 하는데 너무 비효율적이기 때문에

LinkedList라는 클래스를 만들어주자.

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

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            return

        cur = self.head

        while cur.next is not None:
            cur = cur.next
            print("cur is", cur.data)
        cur.next = Node(data)

Linked_list = LinkedList(3)
Linked_list.append(4)
Linked_list.append(5)


#cur is 4

 

링크드 리스트 모든 원소 출력

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

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            return

        cur = self.head

        while cur.next is not None:
            cur = cur.next
            print("cur is", cur.data)
        cur.next = Node(data)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next



Linked_list = LinkedList(3)
Linked_list.append(4)
Linked_list.append(5)

Linked_list.print_all()


#cur is 4
#3
#4
#5

 

 

---

링크드 리스트 원소 찾기

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

linked_list = LinkedList(5)
linked_list.append(12)
print(linked_list.get_node(0).data)
print(linked_list.get_node(1).data)

#5
#12

 

링크드 리스트 원소추가

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        new_node = Node(value)
        node = self.get_node(index)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)

linked_list.print_all()

#5
#12
#8

 

[5] [6] [12] [8] 로 [6] 추가하기

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        new_node = Node(value)
        node = self.get_node(index-1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)

linked_list.add_node(1,6)
linked_list.print_all()

# 5
# 6
# 12
# 8

 

index가 0일 때 처리를 해줘야한다 (index -1)을 해줬는데 -1일경우는 처리를 안해줬으니까!

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        new_node = Node(value) #[6]
        if index == 0:
            new_node.next = self.head #[6] -> [5]
            self.head = new_node # head -> [6] -> [5] -> ...
            return

        node = self.get_node(index-1) #[5]
        next_node = node.next #[12]
        node.next = new_node #[5] -> [6]
        new_node.next = next_node #[6] -> [12]


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)

linked_list.add_node(1,6)
linked_list.print_all()

# 5
# 6
# 12
# 8

---

index번째 원소 삭제

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        new_node = Node(value) #[6]
        if index == 0:
            new_node.next = self.head #[6] -> [5]
            self.head = new_node # head -> [6] -> [5] -> ...
            return

        node = self.get_node(index-1) #[5]
        next_node = node.next #[12]
        node.next = new_node #[5] -> [6]
        new_node.next = next_node #[6] -> [12]

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index -1)
        node.next = node.next.next


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()
#3
#5
#12
linked_list.delete_node(0)
linked_list.print_all()
#5
#12