11. Data Structures ( Arrays & Linked Lists )

 

 

본격적인 자료구조에 대한 공부!

 

Python에서 list를 겁~나게 다뤘는데, 사실 이 List는 고마운 친구였다는 것이다.

 

그 고마운 List의 내부구조를 톺아보자 ㅠㅠ

 

 

 

List가 [1,2,3,4,5] 만 있던 메모리 공간이 있는데 중간에 insert, del 그리고 마지막칸에 메모리가 차 있는데 append를 어떻게 하는지에 대한 궁금증을 해소해야 한다! 별로 안 궁금한데 해소를 해야 한단다..ㅎ

 

어떤 상황에서 어떤 자료구조를 써야 DATA / MEMORY를 효율적으로 쓸 수 있는지를 알기 위하여 자료구조를 배운다.

 

Arrays

 

- 연속된 n개의 자료를 Memory box에 저장한 구조이다. ex) Python의 List

 

- Array의 특징

 

  - Fixed integer length(N) : Initialize할 때 전부 Setting이 된다.

  - 근데 사용자가 Memory를 얼마나 쓸 줄 알고 Memory를 할당하냔 말이다..

 

- 그래서 Python에선 list size를 resize할 때 data가 하나씩 들어올 때마다 0,4,8,16,25.. 이런식으로 사이즈를 늘려간다.

 

 

Linked Lists

 

- Main idea

 

  - Array와는 다르게 메모리상에 흩어져 있는 구조를 만들자

 

   - 다만 이 경우, 쭉 이어져있는 Array와는 달리 첫 번째 메모리 다음 칸의 Data가 뭔지 알기 어렵다

  - 그래서 각 element가 다음 element의 주소를 Pointing 하고 있는 구조를 만든다 --> Linked Lists

 

주소가 꽉 차 있어도 append 할 때 아무대나 memory를 만들어서 data를 더하고, 각 주소만 이전 element와연결

 

 

 

- Linked Lists Node를 class로 코딩해보기

 

class Node():
    def __init__(self,x):
        self.item = x
        self.next = None
a = Node(1)
b = Node(99)
a.next = b
.item
print(a.item)
print(a.next.item)
1
99

 

오랜만에 쓰는 Class문 ;;

 

Singly Linked List

 

- 자료구조라면 가져야할 기본사항

 

 1) Create an empty list

 2) Add / Insert a new item

 3) Retrieving( = Get ) an item

 4) Delete an existing item

 

Inserting an item at i

 

 

 

1) 추가할 Value 를 갖는 Node를 하나 생성한다

 

2) i 번째에 추가할 것이면, i-1번째 항목을 찾는다

 

3) New node의 Next를 i-1번째의 Next로 세팅한다

 

4) i-1번째의 Next를 New node로 세팅한다

 

class Node():
    def __init__(self,x):
        self.item = x
        self.next = None
        
class LinkedList():
    def __init__(self):
        self.first = None
        
    
    def insert(self,x,i):
        new_node = Node(x)
        
        curr = self.first
        pos = 0  # List와 달리 Linked list에선 정해진 index가 없으므로 i-1번째 찾기 위해서 만든 variable
        while pos == i-1: # Traversal 코드
            curr = curr.next
            pos += 1
        
        new_node.next = curr.next
        curr.next = new_node

 

 

- 위의 Case는 i가 0번째인 경우에는 적용시킬 수 없다

 

- 따라서 첫 번째에 바로 값을 집어넣는 경우는 예외 코드를 짜줘야 한다.

 

- 그리고 Linked List 의 item 개수보다 큰 index에 값을 추가하려고 하는 경우도 잡아줘야 한다.

 

class Node():
    def __init__(self,x):
        self.item = x
        self.next = None
        
class LinkedList():
    def __init__(self):
        self.first = None
        
        # LL의 item 개수보다 큰 index에 value를 insert하는 case를 막고자
        self.size = 0
        
    def insert(self,x,i):
        # Insert x at [0]
        if i == 0:
            new_node = Node(x)
            new_node.next = self.first
            self.first = new_node
            
            #Size check
            self.size += 1
        elif i <= self.size:
            new_node = Node(x) 
            curr = self.first
            pos = 0  # List와 달리 Linked list에선 정해진 index가 없으므로 i-1번째 찾기 위해서 만든 variable
            while pos < i-1: # Traversal 코드
                curr = curr.next
                pos += 1

            new_node.next = curr.next
            curr.next = new_node
            #Size check
            self.size += 1
        else :
            print("SIZE를 초과한 Index에요")

생각보다 잡아줘야 할 Gray 영역이 많다;;

 

Get an Item(조회!)

 

- Main idea

 1)  i번째 포지션까지 간다.

 2) 값을 가져온다

 

- Special Case?

 1) i = 0

 2) i >self.size

 3) self.size = 0

 

    def get(self,i):
        # 0 번째 값을 읽는 경우
        if i == 0:
            return self.first.item
        elif i <= self.size:
            pos = 0
            curr = self.first
            while pos < i:
                pos += 1
                curr = curr.next
            return curr.item
        elif i > self.size :
            print("size를 초과해서 Call하셨어요")

 

 

- TEST CASE도 한 번 만들어보기 with insert + get

 

test = LinkedList()
​
test.insert('a',0) # a
test.insert('b',1) # a,b
test.insert('c',1) # a,c,b
test.insert('d',0) # d,a,c,b
test.insert('첫번째',1) # d,'첫번째',a,c,b
​
print(test.get(0),test.get(1),test.get(2),test.get(3))
print(test.get(100))
d 첫번째 a c
size를 초과해서 Call하셨어요
None # 얘 None은 왜 출력되는건지;;

 

 

- 뭐 적절히 잘 동작하는 거 같다 ㅎㅎ..

 

 

Deleting an Item at Position i

 

 

기존 i의 next가 살아있지만, i 로 접근할 방법이 없어졌기에 얘는 delete되었다고 본다

 

 1) Traverse to i-1번째!

 2) i-1 번째 node의 next를 target(i) 의 다음으로 바꾼다. 즉 i-1번째의 next를 i번째 node의 next로 해주면 됨

 

    def delete(self,i):
        # 0 번째를 지우라고 하는 경우
        if i == 0 :
            self.first =  self.first.next
        
        elif i < self.size :
            pos = 0
            curr = self.first
            while pos > i-1:
                pos += 1
                curr = curr.next
            curr.next = curr.next.next
            self.size -= 1
        else : print("size맞춰서 삭제하세요.")

       
test = LinkedList()
​
test.insert('a',0) # a
test.insert('b',1) # a,b
test.insert('c',1) # a,c,b
test.insert('d',0) # d,a,c,b
test.insert('첫번째',1) # d,'첫번째',a,c,b
test.delete(1) # d,a,c,b
test.delete(15) # d,a,c,b
​
​
print(test.get(0),test.get(1),test.get(2),test.get(3))
​
size맞춰서 삭제하세요.
d a c b

 

뭔가 답답하다. 와닿지 않는 기분!!

 

insert / delete 모두 curr이라는 임의의 variable을 함수 def 안에서 만들고 그걸로 값을 더하고 뺀건데,

 

어떻게 이게 본체(?) Linked List에 영향을 주는걸

 

일단 PASS

---

https://sogogi1000inbun.tistory.com/28

관련해서 다른 블로그분의 글이 이해에 도움이 되어 발췌!

역시 그림을 그려서 설명해야 이해하기 편하네

문과생이 이해한 파이썬 연결리스트1(삽입/삭제/출력/탐색/역순)

 

Time Complexity

 

Average Case라고 해봤자 N/2 정도일텐데 Big O 관점에선 N으로 통일!

 

 

 

추가로 고민해 볼 점

 

 

Q. Linked List 를 Reverse하게 코드하는 방법?

Q. Linked List에서 Cycle구조를 Detect하는 방법?

 

 

 

 

머나 먼 코딩의 세계여~