2. 자료구조 - 링크드 리스트

[Python으로 진행하는 자료구조 공부]

 

1. 링크드 리스트

  : 순차적으로 연결된 공간에 데이터를 넣는 구조인 배열과 달리, 저장공간이 떨어져 있어도 포인터로 연결해서 관리하 

    는 데이터 구조

  : 기본 구조

    - 노드 (Node) : 링크드 리스트의 한 데이터블럭 --> (데이터 값, 포인터)의 구조로 이루어짐

    - 포인터 (Pointer) : 각 노드에서, 다음 또는 이전 노드의 연결 정보 (그 노드의 주소 정보)를 가지고 있는 공간

  : 장점 - 미리 사용할 데이터 공간을 할당하지 않아도 됨

  : 단점 - 연결 정보를 담는 공간이 따로 필요하기 때문에 공간 효율이 그리 좋지 않음

          - 원하는 정보에 접근하는데 시간이 걸림

          - 삽입이나 삭제가 일어날 때, 포인터들의 정보를 다시 설정해줘야하는 번거로움이 있음 

 

* 파이썬: 리스트 타입이 링크드 리스트까지 지원함

 

2. 기본 구조 익히기

  1) 기본 노드

     : 파이썬에서는 주로 클래스를 활용하여 노드를 만듦

     : 노드라는 클래스를 만들고, initialize 메소드를 통해 객체 초기 설정을 해줌

     : __init__의 첫 번째 인자인 self를 제외하고, 노드에 실제로 넣을 데이터 값(data)과 다음 노드의 연결 정보 (next)를 입력받음

 

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

 

     2)  노드를 하나 만들었을 때 : 0이라는 값을 저장하고 다음 연결 정보는 None인 상태

 

node1 = Node(0)

 

     3) 다음 노드를 연결: 새로운 노드를 만들고 이전 노드의 포인터에 새로운 노드를 연결해줌

     

node2 = Node(2)
node1.next = node2
head = node1

 

     4) 일괄적인 노드 연결을 위해, 노드를 연결하는 과정을 노드 클래스에 메소드로 만들어서 추가함 

 

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

  def add(data):
    node = head        # 노드 초기 설정--> head
    while node.next:   # node.next가 있는 동안, 즉 마지막 노드까지 이동
      node = node.next
    node.next = Node(data)  # 마지막 노드의 next에 새로운 노드를 생성하고 연결한다
    
    
    
## 연결하기 example
node1 = Node(1)
head = node1
for i in range(2,8):
  add(i)
 

 

2. 링크드 리스트의 복잡한 기능

   : 위의 경우는 마지막에 새로운 노드를 추가함. 노드 사이에 새로운 노드를 추가, 삭제하는 함수를 구현해보고자 함

 

    - 링크드 리스트에서 특정 값 뒤에 노드 추가 및 특정 값을 가진 노드 삭제

 

class Node:
  def __init__(self, data, next = None):
    self.data = data
    self.next = next
    
class NodeEdit:
  def __init__(self, data):
    self.head = Node(data)

## 특정 값의 노드 뒤에 새로운 노드 추가
  def add(prev_data,data):
    if self.head == '':         # head에 데이터가 저장되어 있지 않은 경우
      self.head = Node(data)
    node = self.head
    while node.data == prev_data:    # 특정 값을 가진 노드를 발견할 때까지 다음 노드로 이동
      node = node.next
    new = Node(data)            # 새로운 노드를 만듦
    prev_next = node.next       # 원래 노드의 포인터값을 새로운 변수에 저장시킴
    node.next = new             # 노드에 새로운 노드를 연결
    new.next  = prev_next       # 새로운 노드에 다음 노드를 연결
    
## 특정 값의 노드를 삭제
  def delete(data):
    if self.head == '':
      print("There is not a node with that value.")
      return
    if self.head.data == data:   # case 1) self.head를 삭제해야 하는 경우
      temp = self.head           # 해당 노드를 삭제해야하기 때문에 임의의 변수에 우선 저장함
      self.head = self.head.next
      del temp
    else:      
      node = self.head
      while node.next:            # case 2) head가 아닌 임의의 노드를 삭제해야 하는 경우
        if node.next.data == data:
          temp = node.next
          node.next = node.next.next      # 바로 뒤의 노드를 삭제하기 때문에, 그 다음 노드에 연결
          del temp
        else:                
          node = node.next
          
        

 

3. 더블 링크드 리스트

   : 위에서 다룬 링크드 리스트는 모두 다음 노드로의 연결 정보만 있었다면, 더블 링크드 리스트는 다음 노드뿐만 아니

     라 이전 노드에의 연결 정보도 가지고 있음. 즉, 포인터가 양방향으로 있음

    : 한쪽으로의 탐색만 가능한 일반 링크드 리스트의 단점을 극복

 

    - 기본 구조

 

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

 

  - 활용) 특정 값을 가진 노드 앞에 새로운 노드를 삽입

 

class Node:
  def __init__(self, data, prev = None, next = None):
    self.data = data
    self.prev = prev
    self.next = next
    
class NodeEdit:
  def__init__(self, data):
    self.head = Node(data)      
    self.tail = self.nead    # 노드가 하나만 있는 초기 상태이므로 tail=head
  
  def search_from_tail(self, data):
    if self. head == None:
      return
    node = self.tail
    while node:
      if node.data == data:
        return node
      else:
        node = node.prev
          
  def insert_before_node(self, prev_data, data):
    if self.head == None:
      self.head = Node(data)
    else:
      node = self.tail
      while node.data != prev_data:
        node = node.prev
        if node == None:      # 이 링크드 리스트에 해당하는 값을 가진 노드가 없음
          print("해당하는 노드가 없습니다.")
          return
      new = Node(data)
      prev_link = node.prev
      prev_link.next = new       
      new.prev = prev_link
      new.next = node
      node.prev = new
 

 

++

링크드 리스트는 포인터를 재 설정하는 점이 많이 헷갈리는 것 같다.

더 연습을 해야겠다 :)