Linked List 1

Array List와 Linked List의 차이

Array List는 메모리상 즉 물리적으로 연속적으로 저장

Linked List는 메모리상 즉 물리적으로는 비연속적으로 저장되어 있지만,

각각의 node가 next node의 메모리 주소값을 가리킴으로써 논리적인 연속성을 갖게 된다.

다만 next node의 address도 추가적으로 저장해야 하기 때문에 데이터하나당 차지하는 메모리가 

더 커지게 된다.

 

 

예제 코드

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

1.self는 객체 자기 자신.(호출한 놈)을 가리킨다

자바에서의 this와 파이썬의 self는 동일하다.

2.Node 클래스 안에 있는 
def__init__(self, value=0, next=None)는 
생성자(constructor)를 가리킨다.

 

 

보충자료1

A관점, B관점, C관점, D관점

 

 

보충자료2

→참조형을 C언어의 pointer라고 생각해봐

 

 

 

 

실제로 구현해 보기

class Node:
    def __init__(self, value=0, next = None): #노드 클래스의 생성자
        self.value = value
        self.next = next

class LinkedList(object):
    def __init__(self): #여기서 self는 ll을 의미한다.
        #self.head라는 변수에는 주소(번지)가 저장된다. or head는 None을 가리킨다.
        self.head = None  

    #append
    def append(self, value):
        new_node = Node(value) #new_node는 Node(1)을 가리킨다.
        #만약에 head라는 변수에 저장된 주소를 따라가 보니 None이 저장되어 있다면,
        if self.head is None: 
            self.head = new_node  #self.head라는 변수에 new_node의 주소(번지)가 저장된다. or head는 new_node를 가리킨다.
       
       
        #맨 뒤의 node가 new_node를 가리켜야 한다.
        else:
            current = self.head  #self.head변수에 저장된 주소를 current변수에 대입한다. 그러면 current는 head가 가리키는 곳을 똑같이 가리킨다.
            while(current.next): #current도 참조형이라는 것을 잊지 말자!!! current가 가리키는 node의 next에 주소값이 있다면, 즉 next노드를 가리키고 있다면 ////current를 포인터라고 생각해
                current = current.next #current.next에 저장된 주소를 current변수에 대입한다. 그러면 current는 current.next가 가리키는 곳을 가리킨다. 
            current.next = new_node #current.next의 주소가 존재하지 않아서 while문을 빠져나온 경우에 current.next는 new_node가 가리키는 곳을 가리킨다.

    
    # get
    def get(self, idx):
        current = self.head
        for _ in range(idx):
            current = current.next
        return current.value
  

    # insert_at
    def insert_at(self, idx, value):
        new_node = Node(value) #새로 추가하고자 하는 노드를 생성한다.
        new_node.value = value #new_node가 가리키는 node의 value에 value를 대입한다.
        current = self.head    #head가 가리키는 곳을 current가 가리킨다.

        if idx == 0:                  #index가 0이면
            self.head = new_node      #new_node가 가리키는 곳을 head가 가리킨다. 
            self.head.next = current  #head가 가리키는 node의 next는 current가 가리키는 곳을 가리킨다. 
        else:
            for _ in range(idx - 1):       #삽입하고자하는 index의 바로 직전까지간다. 
                current = current.next     #current는 current.next가 가리키는 곳을 가리킨다.
            new_node.next = current.next   #new_node가 가리키는 Node의 next는 current가 가리키는 곳의 next를 가리킨다.
            current.next = new_node        #current가 가리키는 Node의 next는 new_node를 가리킨다. 



    #remove1
    def remove_at(self, idx):
        current = self.head               #head가 가리키는 곳을 current가 가리킨다.

        if idx == 0:                      #index가 0이면
            self.head = current.next      #head는 current가 가리키는 node의 next가 가리키는 곳을 가리킨다.

        for _ in range(idx - 1):          #삭제하고자 하는 노드 직전까지 접근한다.
            current = current.next
        current.next = current.next.next  #current의 next는 current.next가리키고 있는 Node의 다음 Node를 가리킨다.

	
    #remove2
    def remove(self, idx):
        if idx == 0:
            self.head = self.head.next # garbage collector가 알아서 처리해준다.
        else:              
            current = self.head               #head가 가리키는 곳을 current가 가리킨다.
            for _ in range(idx-1):            #삭제하고자 하는 노드 직전까지 접근한다.
                current = current.next        #current는 current.next가리키는 곳을 가리킨다. 
            current.next = current.next.next  #current의 next는 current.next가리키고 있는 Node의 다음 Node를 가리킨다


    # all_nodes
    def all_nodes(self):
        current = self.head
        while current.next:
            print(str(current.value) + "->", end=' ')
            current = current.next
        print(current.value)


ll = LinkedList()
ll.append(100)
ll.append(200)
ll.append(300)
ll.append(400)



ll.all_nodes()

print(ll.get(0))
print(ll.remove_at(1))
print(ll.get(1))

ll.all_nodes()

 

 

실제로 구현해 보기 → append

 

 

 

1단계

append구현1

 

 

 

 

 

2단계

 

 

 

 

3단계

 

 

 

실제로 구현해 보기 → get

 

 

 

 

 

실제로 구현해 보기 → insert_at

 

 

 

실제로 구현해 보기1 →remove

 

 

 

실제로 구현해 보기2 →remove