[패캠 네카라쿠배 2기] 2차 테스트 - 7일차

대표적인 데이터 구조: 링크드 리스트 (Linked List)

1. 링크드 리스트 (Linked List) 구조

• 연결 리스트라고도 많이 함
• 구조는 단순한데 구현하기 복잡하고 헷갈리는 부분이 많다 
• 프로그래밍 퀴즈를 낼 때(가벼운 면접) 등에서 링크드 리스트 문제를 내는 경우 많다
• 배열은 순차적으로 연결된 공간을 예약을 해놓고(확보를 해놓고) 거기에 데이터를 하나씩 넣어서 나열하는 데이터 구조// 그러므로 새로운 정보를 추가할 수 없음. 이런 단점을 해결하기 위해 나온 것이 링크드 리스트다
• 링크드 리스트는 예약을 해놓지 않고 필요할 때마다 추가// 공간을 만들고 그 안에 데이터와 다음 데이터 주소를 적는다 / 다음 데이터는 어느 공간이든 간에 새로운 노드를 만들고 이 노드의 주소를 앞에 있는 노드의 포인터에 넣는다// 그러므로 맨앞 노드의 주소만 알면 전체 데이터를 확인할 수 있다(A를 알면 다음 데이터 주소가 있고 그 다음 B를 가고 다음 데이터 주소를 보고 C를 찾아가고 계속 이어지다가 마지막 데이터 주소가 null일 때 끝이라는 것을 보면 된다) // 즉 링크드 리스트는 무한정으로 추가할 수 있다
• 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
• 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원

• 링크드 리스트 기본 구조와 용어
  • 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성
  • 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

* 일반적인 링크드 리스트 형태

: 배열과 달리 특정 데이터를 저장할 때 저장할 공간과 그 뒤에 나올 데이터가 저장되어 있는 공간을 가리키는 주소값을 

적은 공간 ([데이터 + 다음 데이터 가리키는 주소[포인터]][노드])

(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

2. 간단한 링크드 리스트 예

Node 구현

• 보통 파이썬에서 링크드 리스트 구현시, 파이썬 클래스를 활용함
  • 파이썬 객체지향 문법 이해 필요 : 
  • 참고: https://www.fun-coding.org/PL&OOP1-3.html

파이썬과 객체지향 프로그래밍: 객체지향 (class와 object) - 잔재미코딩

In [1]:

class Node: // 두 가지 데이터를 넣어야 하므로 클래스를 넣는 것이 더 수월하다

  def __init__(self, data): // 이 클래스가 객체화될 때마다 넣을 것들을 생성한다 [생성자]

    self.data = data

    self.next = None

 

In [3]:

class Node:

 def __init__(self, data, next=None): // self는 클래스의 메서드에 인자로 붙지만 실제 인자는 아니다 

                                             // data와 다음 노드를 가리킬 주소(포인터)를 next라는 인자로 넣는다.

                                                만약 두번째 인자를 안 넣으면 디폴트 None

      self.data = data

      self.next = next

 

Node와 Node 연결하기 (포인터 활용) : 

node1 = Node(1)

node2 = Node(2)

node1.next = node2 // 링크용! 주소는 주소를 주는 게 아니라 클래스로 만든 객체 자체를 넣는다 

head = node1 // 첫 노드를 알아야 링크드 리스트 가능

 

링크드 리스트로 데이터 추가하기

class Node:

 def __init__(self, data, next=None):

self.data = data

self.next = next

 

​def add(data): // 원래 Node 클래스의 메서드로 쓰지만 여기선 복잡하니까 따로 함수 

node = head

while node.next: // 링크드 리스트에서 데이터를 추가할 때 맨 끝의 노드에 연결

                       / while문으로 node.next 가 있으면 (true)면 node를 다음 노드의 주소로 바꾸고 

  node = node.next

//while문이 node.next = None이어서 끝나면 

node.next = Node(data) // 인자로 받는 data로 마지막 Node의 주소에

                                     지금 생성한 node의 주소가 들어가서 추가가 된다 

// 내가 헷갈려하는 부분 

 

 

node1 = Node(1) // 첫노드 

head = node1 // 처음을 알아야 링크드 리스트 사용 간으 

for index in range(2, 10):

add(index) // add()에 data 2~9를 넣어 Node(2)~Node(9)를 추가한 linked list를 구현하게 된다 

 

 

링크드 리스트 데이터 출력하기(검색하기)

In [10]:

node = head

while node.next: // None 이 아닐 때만 

   print(node.data) 

   node = node.next // 다음 노드를 가르키도록 

print (node.data)

1 2 3 4 5 6 7 8 9

 

3. 링크드 리스트의 장단점 (전통적인 C언어에서의 배열과 링크드 리스트)

• 장점
  • 미리 데이터 공간을 미리 할당하지 않아도 됨
    • 배열은 미리 데이터 공간을 할당 해야 함
• 단점
  • 연결을 위한 포인터 주소를 넣기 위해 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  • 배열은 인덱스 번호로 바로 해당 데이터를 가져올 수 있는 반면
  • 링크드 리스트는 첫 노드부터 순차적으로 주소를 찾아가야 하므로 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제 또는 삽입 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

4. 링크드 리스트의 복잡한 기능1 (링크드 리스트 데이터 사이에 데이터를 추가)

• 링크드 리스트는 유지 관리에 부가적인 구현이 필요함 
• 아래 그림의 37처럼 중간에 삽입하기 위해서는 12에서 37을 가리키고 37에서 99를 가리켜야 한다

(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

In [11]:

 

node = head

while node.next:

   print(node.data)

   node = node.next

print (node.data)

1 2 3 4 5 6 7 8 9

In [12]:

node3 = Node(1.5)

//이 값을 1과 2 사이에 넣고 싶을 때

In [13]:

node = head

search = True

while search:

  if node.data == 1:

     search = False // data가 1인 애를 찾으면 그 값을 가진 채 while문이 끝난다 

  else:    

  node = node.next // 1을 못 찾으면 계속 node는 node의 next가 된다​

     node_next = node.next // data가 1인 node가 가진 주소가 다음 node의 주소니까

node.next = node3 // data가 1인 node가 가리키는 주소를 추가하는 node3로 하고

node3.next = node_next  // node3의 포인트 즉 가리키는 다음 주소 값을 node_next

                                     (1인 data가 원래 가리켰던 data가 2였던 노드의 주소)                                                

 

node = head

while node.next:

print(node.data)

node = node.next

print (node.data)

1 1.5 2 3 4 5 6 7 8 9

 

5. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

: 각각의 노드를 저장, 생성할 수 있는 클래스 만들기 

 

In [15]:

class Node:

 def __init__(self, data, next=None):

   self.data = data

   self.next = next

 

class NodeMgmt: //링크드 리스트를 관리할 수 있는 클래스. 맨 앞에 노드의 값을 가질 수 있는 걸 만들어놓는다

   def __init__(self, data): 

     self.head = Node(data)

   

    def add(self, data): //  해당 링크드 리스트의 맨 끝에 노드를 추가하는 함수

       if self.head == '': // 방어 코드 : 만약 head값이 없으면 추가할 데이터를 가지고 맨 앞 노드를 만든다 

          self.head = Node(data)

       else:

          node = self.head

          while node.next:  //none이 아니면 

              node = node.next // node는 다음 주소를 가지도록 

          node.next = Node(data)

                   // node.next = none으로 while문이 끝났을 때 마지막 node.next는 새롭게 넣은 Node(data)가 되도록

   

    def desc(self): // 해당 링크드 리스트의 전체를 출력할 수 있는 함수 

            node = self.head

            while node: // node가 있으면 

                 print (node.data) // 해당 node의 data를 가져오고 

                 node = node.next // 다음으로 넘어가 또 node를 불러온다 

 

linkedlist1 = NodeMgmt(0) // 0이라는 data를 가진 node가 객체로 만들어진다 

linkedlist1.desc() 

0

 

for data in range(1, 10):

linkedlist1.add(data)

linkedlist1.desc()

0 1 2 3 4 5 6 7 8 9

6. 링크드 리스트의 복잡한 기능2 (특정 노드를 삭제)

• 다음 코드는 위의 코드에서 delete 메서드만 추가한 것이므로 해당 메서드만 확인하면 됨

1. head 삭제 

2. 마지막 노드 삭제 

3. 중간 노드 삭제 

// 각각의 경우의 수가 있고 이를 구현하는 것이 매우 복잡 

 

class Node:

      def __init__(self, data, next=None):

              self.data = data

              self.next = next

 

class NodeMgmt:

       def __init__(self, data):

              self.head = Node(data)

       def add(self, data):

          if self.head == '':

            self.head = Node(data)

         else:

            node = self.head

            while node.next:

                 node = node.next

            node.next = Node(data)

 

def desc(self):

        node = self.head

        while node:

              print (node.data)

              node = node.next

 

def delete(self, data):

         if self.head == '': //head가 없으면 

             print ("해당 값을 가진 노드가 없습니다.")

             return // 끝낸다. 여기까지 방어 코드 

          if self.head.data == data: // head에 있는 data가 data인 경우 (head 삭제하는 경우)

              temp = self.head

              self.head = self.head.next // 첫 node를 삭제할 거니까 head를 다음 주소로 바꾸고 

              del temp // 첫 node 삭제 

         else:

                 node = self.head // 삭제할 데이터가 head가 아닌 경우 

                 while node.next: // 2번째가 삭제할 데이터인지 확인하는 것

                   if node.next.data == data:

                        temp = node.next

                        node.next = node.next.next // 2번째를 삭제하니까 첫번째가 가리키는 주소인 node.next가 세번째 주소를 가리키도록 

                        del temp

                        return // 

                   else:

                        node = node.next

 

테스트를 위해 1개 노드를 만들어 봄

In [19]:

linkedlist1 = NodeMgmt(0)

linkedlist1.desc()

0

 

head 가 살아있음을 확인

linkedlist1.head

<__main__.Node at 0x1099fc6a0> // 0 node가 생성된 것을 확인할 수 있다

head 를 지워봄(위에서 언급한 경우의 수1)

 

linkedlist1.delete(0)

 

다음 코드 실행시 아무것도 안나온다는 것은 linkedlist1.head 가 정상적으로 삭제되었음을 의미

 

다시 하나의 노드를 만들어봄

 

 

linkedlist1 = NodeMgmt(0)

linkedlist1.desc()

0

이번엔 여러 노드를 더 추가해봄

 

for data in range(1, 10):

linkedlist1.add(data)

linkedlist1.desc()

0 1 2 3 4 5 6 7 8 9 // 0은 위에서 만든 

노드 중에 한개를 삭제함 (위에서 언급한 경우의 수2)

 

 

linkedlist1.delete(4)

 

특정 노드가 삭제되었음을 알 수 있음

 

 

linkedlist1.desc()

0 1 2 3 5 6 7 8 9

 

linkedlist1.delete(9)

 

linkedlist1.desc()

0 1 2 3 5 6 7 8

 

# 링크드 리스트 강의 4번

연습1: 위 코드에서 노드 데이터가 2인 노드 삭제해보기

 

node_mgmt.delete(2)

node_mgmt.desc()

 

연습2: 위 코드에서 노드 데이터가 특정 숫자인 노드를 찾는 함수를 만들고, 테스트해보기
테스트: 임의로 1 ~ 9까지 데이터를 링크드 리스트에 넣어보고,

데이터 값이 4인 노드의 데이터 값 출력해보기

 

class Node:

def __init__(self, data):

self.data = data

self.next = None​

 

class NodeMgmt:

  def __init__(self, data):

     self.head = Node(data)

  def add(self, data):

      if self.head == '':

          self.head = Node(data)

      else:

node = self.head while node.next: node = node.next node.next = Node(data)​ def desc(self): node = self.head while node: print (node.data) node = node.next​ def delete(self, data): if self.head == '': print ('해당 값을 가진 노드가 없습니다.') return if self.head.data == data: # 경우의 수1: self.head를 삭제해야할 경우 - self.head를 바꿔줘야 함 temp = self.head # self.head 객체를 삭제하기 위해, 임시로 temp에 담아서 객체를 삭제했음 self.head = self.head.next # 만약 self.head 객체를 삭제하면, 이 코드가 실행이 안되기 때문! del temp else: node = self.head while node.next: # 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우 if node.next.data == data: temp = node.next node.next = node.next.next del temp pass else: node = node.next def search_node(self, data): node = self.head while node: if node.data == data: return node else: node = node.next

 

In [ ]:

 

 

 

# 테스트node_mgmt = NodeMgmt(0)for data in range(1, 10): node_mgmt.add(data)​node = node_mgmt.search_node(4)print (node.data)

 

7. 다양한 링크드 리스트 구조

• 더블 링크드 리스트(Doubly linked list) 기본 구조 // 링크드 리스트의 변형된 구조
  • 이중 연결 리스트라고도 함 
  • 데이터가 엄청 많을 때 검색할 때 매우 어려움(왜냐하면 head부터 포인터를 타고타야 하니까) 
  • 더블 링크드 리스트 : 처음과 끝 양쪽에서 검색 가능한 것 (그러므로 내가 찾고자 하는 자료가 전반부인지 후반부인지만 알면 찾기 용이하다) // 방법: 이전 데이터 주소도 추가를 한다 
  • 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
    

    

    (출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

class Node:

  def __init__(self, data, prev=None, next=None): // prev, next를 둘 다 넣어준다 

    self.prev = prev

    self.data = data

    self.next = next​

 

class NodeMgmt: 

  def __init__(self, data): // default 데이터 

    self.head = Node(data) // head 

    self.tail = self.head // 뒤에서부터 검색할 수도 있으니까 tail도 있다​

 

  def insert(self, data): // 맨 뒤에다 하나 추가하는 

  if self.head == None: // head가 없으면 head를 만든다

    self.head = Node(data)

    self.tail = self.head // tail도 만든다 (만약 tail이 있으면 head가 있다는 말이고 그 말은 node가 있다는 말)

  else:

    node = self.head // 그러므로 head를 node라는 변수에 넣어놓고

    while node.next:

// 만약 node.next가 마지막 주소라면 None그러므로 이 반복문이 계속 된다는 건 마지막 주소가 아니라는 것 (node의 끝을 찾아가려고 하는 부분)

    node = node.next // 마지막 node를 가리키는 주소 

    new = Node(data) // new라는 이름의 새로운 node를 만들고  [node - node.next - new]

node.next = new // 다음 node의 주소를 new로 정하고 (node기준, 다음을 new)

new.prev = node // 새로운 것의 이전 주소를 node (new기준, 이전을 prev)

self.tail = new // 새로운 node가 생성되었으니까 맨끝을 수정해준다

​

desc는 나열이기 때문에 위와 다르지 않음

def desc(self): 

  node = self.head

  while node: //none이 아닌 동안 

   print (node.data)

   node = node.next // 다음 주소를 넣는다 

 

test해보기

double_linked_list = NodeMgmt(0) // 초기에 넣을 값 

  for data in range(1, 10):

   double_linked_list.insert(data)

   double_linked_list.desc()

0 1 2 3 4 5 6 7 8 9

 

 

연습3: 위 코드에서

노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수를 만들고, 테스트해보기
- 더블 링크드 리스트의 tail 에서부터 뒤로 이동하며, 특정 숫자인 노드를 찾는 방식으로 함수를 구현하기
- 테스트: 임의로 0 ~ 9까지 데이터를 링크드 리스트에 넣어보고,

데이터 값이 2인 노드 앞에 1.5 데이터 값을 가진 노드를 추가해보기

 

class Node:

   def __init__(self, data, prev=None, next=None):

       self.prev = prev

       self.data = data

       self.next = next

​class NodeMgmt:

      def __init__(self, data):

            self.head = Node(data)

            self.tail = self.head​

      def insert(self, data):

             if self.head == None:

                  self.head = Node(data)

                  self.tail = self.head

             else: node = self.head

          while node.next:

             node = node.next

             new = Node(data)

             node.next = new

          new.prev = node

          self.tail = new​

def desc(self):

node = self.head

while node:

print (node.data)

node = node.next

 

def search_from_head(self, data): // 앞부터 검색 

if self.head == None: // 방어 코드 (아예 head부터 없으면 false되도록) 

return False

node = self.head // node에 head를 넣고 

while node:

  if node.data == data: // 우리가 넣은 인자 data와 같으면 

    return node //해당 node를 반환한다

  else:

   node = node.next // 다음 node를 또 살핀다 

// while문이 끝났다는 건 계속 일치하는 data를 찾았는데 return값이 없다는 것이므로 return false

return False

 

def search_from_tail(self, data):

 if self.head == None:

  return False

node = self.tail // 뒤에서부터 찾기 시작 

while node: // None이 아닐 때 

  if node.data == data: // 찾고 있는 값과 같으면 반환 

   return node

  else: // 다르면 그 앞 값으로 계속 

   node = node.prev

 return False // while문이 끝나면 false반환 

 

def insert_before(self, data, before_data): //self, data, before_data - before_data값을 가진 노드 앞에 data를 가진 노드를 만들겠다 //뒤에서부터 오는 것이기 때문에 before_data가 사실 더 뒤에 있는 거 (뒤에서 봤을 때 before)

// 그러므로 before앞에 data를 넣어야 하니까 찾는 값이 before와 같으면 그 앞에 insert하면 된다 

 

  if self.head == None:

     self.head = Node(data) // 만약 head가 없으면 node가 아예 없는거니까 data를 가진 node를 만들어주면 됨

     return True

  else: // head가 있으면

    node = self.tail // 뒤에서부터 검색(연습4의 문제 조건이니까)

    while node.data != before_data: // tail부터 시작해서 node에 있는 data가 before_data가 아니라면  

       node = node.prev // 앞으로 하나씩 움직이면서 확인한다

        if node == None:

          return False // 찾은 뒤 그 앞에 insert해야하는데 아예 없으니까 return false

    new = Node(data) // while문을 벗어났다는 것은 같은 것을 찾았다는 것 그러므로 new를 만들어서 

    before_new = node.prev // 기준으로 하고 있는 node 앞을 before_new로 잡는다

    before_new.next = new // 원래 node앞에 있는 node를 가리키도록 : before_new.next(다음에 오도록 가리킬 주소 : 포인터) 는 새로 생성된 new를 가리키도록 

new.prev = before_new // 새로 생성한 new를 before_data 즉 node의 앞에 넣어야. 근데 before_new는 before_data와 일치한 node.prev. 그러므로 new를 node앞에 넣으면 before_new의 뒤에 넣어야함. 그러므로 new의 앞은 before_new 

new.next = node // before_data값 앞에 data(new로 생성)를 삽입하는 건데

                           before_data를 찾아서 일치한 것이 node니까 new는 node의 앞에 있어야 함. 

                           그러므로 new의 기준으로 next가 node

node.prev = new// 위와 똑같은 말. but 더블이라 각각 prev, next가 있어야 

return True

 

테스트 : 2 앞에 1.5 넣기 

double_linked_list = NodeMgmt(0)

for data in range(1, 10): 

   double_linked_list.insert(data)

double_linked_list.desc()

0 1 2 3 4 5 6 7 8 9

In [15]:

node_3 = double_linked_list.search_from_head(3)

node_3.data // 만약 node_3을 치면 객체가 반환된다 

Out[15]:

3

In [18]:

double_linked_list.insert_before(1.5, 2)

double_linked_list.desc()

0 1 1.5 2 3 4 5 6 7 8 9

In [19]:

node_3 = double_linked_list.search_from_tail(1.5)

node_3.data

Out[19]:

1.5

 

 

연습4: 위 코드에서 노드 데이터가 특정 숫자인 노드 뒤에 데이터를 추가하는 함수를 만들고, 테스트해보기
- 더블 링크드 리스트의 head 에서부터 다음으로 이동하며, 특정 숫자인 노드를 찾는 방식으로 함수를 구현하기
- 테스트: 임의로 0 ~ 9까지 데이터를 링크드 리스트에 넣어보고, 데이터 값이 1인 노드 다음에 1.7 데이터 값을 가진 노드를 추가해보기

In [ ]:

class Node: def __init__(self, data, prev=None, next=None): self.prev = prev self.data = data self.next = next​class NodeMgmt: def __init__(self, data): self.head = Node(data) self.tail = self.head def insert_before(self, data, before_data): if self.head == None: self.head = Node(data) return True else: node = self.tail while node.data != before_data: node = node.prev if node == None: return False new = Node(data) before_new = node.prev before_new.next = new new.next = node return True​ def insert_after(self, data, after_data): if self.head == None: self.head = Node(data) return True else: node = self.head while node.data != after_data: node = node.next if node == None: return False new = Node(data) after_new = node.next new.next = after_new new.prev = node node.next = new if new.next == None: self.tail = new return True​ def insert(self, data): if self.head == None: self.head = Node(data) else: node = self.head while node.next: node = node.next new = Node(data) node.next = new new.prev = node self.tail = new​ def desc(self): node = self.head while node: print (node.data) node = node.next

 

In [ ]:

 

 

 

node_mgmt = NodeMgmt(0)for data in range(1, 10): node_mgmt.insert(data)​node_mgmt.desc()​node_mgmt.insert_after(1.5, 1)node_mgmt.desc()