[알고리즘] 링크드 리스트 구현하기 / 노드 이해! (주말공부)

노드라는 클래스를 만들고

Class Node:

def _init_(self,data)

data를 받아서

self.data에 data를 저장한다.

 

data는 파라메터고, 

data는 저장변수다.

 

Class Node: 

 def _init_(self,data):

         self.data = data

         self.next =None #이 자체의 next는 없다

 

node = Node(3)

 

Node클래스에 3이 저장될거고, 이 node가 가리키는 노드는 없다(none)

(-> 화살표 없이 3만 있는 것)

 

a_node = Node(5)

b_node = Node(12)

 

만약, a_node.next = b_node 라고 하면

이제 연결된 [5]->[12] 가 되겠지

 

이렇게 next로 하나씩 연결해주면 1억개면 너무 번거로우니

이래서 필요한게 linkedList 클래스

 

링크드리스트는 맨 앞칸(=head node)만 가지고 있으면 된다.

링크드리스트는 Head node라고 불리는 것만 들고 있다.

딱 맨 앞칸만 저장해놓는 것

 

다음칸을 보려면 next를 통해서 찾아가야 한다.

 

 

 

Class Node:

 def _init_(self,data):

         self.data = data

 

node 안에는 데이터와, next를 가리키는 화살표가 있어야 한다.

-> 데이터와 next를 주입받아야 하는데 그럼 contructor를 통해 주입받기

[def __init__(self): 하면 컨스트럭터 만들 수 있음]

 

class Node:

     def __init__(self, data): #우리는 데이터라는 걸 입력받아 self.data에 저장해야하니 data 써주기

     self.next = None

 

 

a_node = Node(5)

b_node = Node(12)

 

a_node.next = b_node

 

print(a_node.next)

라고 하면 0x108d57550 하고 외계어 나옴

따라서 아까 저장한 data까지 써서 숫자 프린트하기 

print(a_node.next.data)

 

class LinkedList:

         def __init__(self,data):

                self.head = N

 

 

이제 head 뒤에 계속 노드들을 연결하고 싶음!!

그럼 node를 연결하는 함수를 만들어주어야 한다.

append함수를 이용해서 노드 연결하기

 

class LinkedList:

         def __init__(self,data):

                self.head = N

 

        def append(self,data):

             

 

그럼 이렇게 head 뒤에다가 Node를 붙이면 될까?

   self.head.next=Node(data)

 

정답은 No !!!!!

우리는 head에 붙이고 싶은게 아니라 node에 계속 연결하면서 붙이고 싶은 것

 

그럼 current 라는 객체를 새로 만들기

current 는 현재 가리키고 있는 위치!!

 

current = self.head

current = current.next

이런식으로 current 가 계속해서 맨 끝까지 이동할 수 있게 해주기

 

 

그럼 맨 끝인지는 어떻게 알 수 있을까?

--> 맨 끝 노드는 next가 none 임

 

while문을 사용해서 current.next값이 None이 될때까지 이동해주기

 

while current.next == None:

          current = current.next

 

-> current.next값이 None 이 될때까지 current = current.next 작업을 해줘라

 

class LinkedList:

         def __init__(self,data):

                self.head = N

 

        def append(self,data):

                 current = self.head

                 while current.next =None:

                               current=current.next

                  current.next =  Node(data) 

 

 

만약 current.next값이 None이 되면 while문을 빠져나오고 아래 식이 실행됌

current.next =Node(data)

드디어 current.next에다가 새로운 node 를 생성해서 붙여주는 것

 

잠깐!!

근데 만약 head에 값이 없으면 ㅇㅅㅇ?

head가 none인데 head뒤에 next를 붙이면 에러가 날 것!!

따라서 예외처리를 위에서 미리 해주자궁

 

if self.head is None:

         self.head=Node(data)

         return 

 

--> self.head에 값이 안들어있다면 self.head에 데이터가 담긴 node를 담고 return으로 함수 끝내주기

 

class LinkedList:

         def __init__(self,data):

                self.head = N

 

        def append(self,data):

                 if self.head is None:

                 self.head=Node(data)

                 return 

                 self.head.next = Node(data)

                 current = self.head

                 while current.next =None:

                               current=current.next

                current.next =  Node(data) 

 

linked_list = LinkedList(3)

linked_list.append(4)

linked_list.append(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, data):
        if self.head is None:
            self.head = Node(data)
            return

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

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

 

실행되는 순서 확인하기

---

* self

클래스의 구성을 취득할 때에 정형의 구문으로써 기억해두면 괜찮은 것 같다.

 

__init__()은 반드시 첫 번째 인수로 self를 지정해야한다. self에는 인스턴스 자체가 전달되어 있다. 이로 인해, 최과 메소드 내에 인스턴스 변수를 작성하거나, 참고하는 것이 가능해진다. 클래스를 생성할 때에 지정한 인수는 초기화 메소드의 2 번째부터 작성해 나가면 된다.

class SomeClass:
    def __init__(self,something):#constructor
        self.something = something

 클래스 구성에서 정보를 유지하기 위한 중요한 구성으므로 빼놓을 수 없는 것이라고 생각하면 좋을 것 같다. 이 구문에 의해 객체 생성할 때, 정보의 추가 기재를 간단히 할 수 있다.

 예를 들어, 여러 개의 정보를 변수로하는 클래스 구문에서의 처리를 실행하고 싶은 경우는 다음과 같이 쓸 수 있다.

class MyStatus:
    def __init__(self,age,name,height,weight):
        self.age = age
        self.name = name
        self.height = height
        self.weight = weight

    def print_name(self):
        print(self.name)

    def print_age(self):
        print(self.age)

    def print_height(self):
        print(self.height)

    def print_weight(self):
        print(self.weight)