자료구조 #1 링크드리스트

class

class : 똑같은 무엇인가를 계속 만들어낼 수 있는 설계 도면
Object : class에 의해 만들어진 무언가
인스턴스 : class에 의해 만들어진 객체
method : class 내부에 정의된 함수
cf. 객체와 인스턴스의 차이

• 클래스에 의해서 만들어진 객체를 인스턴스라고도 한다.

• a를 단독으로 지칭할 때: 'a는 객체'

• 클래스와 연관지어서 지칭할때: 'a는 Cookie의 인스턴스'
  [출처][Python] Class와 init 이해|작성자 N or N

링크드 리스트

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

Node라는 class를 만든다. Node는 data를 초기화 해주고 next는 None으로 만든다.
data1은 파라미터 = 매개변수
data2는 클래스 내부에서 사용되는 저장되는 변수
클래스내에 함수가 선언 될 때에는 첫번째 인자로 무저건 self가 와야한다.
init메소드는 초기화를 위한 메소드, 인스턴스화를 실시할 떄 반드시 처음에 호출되는 특수한 함수, 오브젝트 생성과 관련하여 데이터의 초기를 실시 하는 함수
다른말로 constructor라고 부른다.
-> 객체이 초기 값을 설정할 필요가 있음(오류나서),

init관련 링크 https://blog.naver.com/n2ll_/221442949008

self? -> init은 무조건 self인자를 첫번째로 받는다. self는 인스턴스 그 자신을 뜻한다. -> 인스턴스를 초기화 하는 init함수에서 self는 인스턴스를 초기화 하기 위해 생성된 인스턴스를 받아오는 역활

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

LinkedList라는 클래스를 생성 링크드 리스트는 head 데이터만 있으면 된다.
인스턴스 = LinkedList(value)하면 self.head에 Node(value)를 적용시킨다.
인스턴스.append(value) 하면 self.next가 None인지 파악하고 None이 아니면 cur.next로 다음으로 넘어가기 None이면 next에 저장
인스턴스.print_all() self.head를 Cur에 저장 cur을 while반복문으로 None이 나올 때 까지 반복 print(cur.data)로 현재 데이터 출력, cur = cur.next로 다음 원소 넘어가기

링크드 리스트 원소 찾기

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

링크드 리스트는 head부터 순차적으로 넘어가게 되어 있어서 원하는 index를 찾기 위해서 head에서 next로 넘어가는 순간 count를 1씩 올리면 원하는 index를 찾을 수 있다.

링크드 리스트 원소 추가

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

1-> 2-> 3 링크드 리스트는 이렇게 되어 있어서 1과 2 사이에 무언가를 추가하려면
->를 제거 해아고 그 사이에 추가하고 ->로 이어줘야 한다.
1. 현재 노드 저장
2.new_node에 새로운 value를 저장
3.next_node에 현재 값의 다음 값을 저장(사라지기 떄문에 저장해야한다.)
4.node,next로 현재 뒤에 new_node를 붙이기
5.new_node.next로 전에 next_node를 붙이기