데이터 구조 및 분석 : Linked List

본 게시글은 Edwith 문일철 교수님의 데이터 구조 및 분석: Linear Structure and Dynamic Programming을 듣고 정리한 내용입니다.

1. Linked List

• 한줄 요약 : array와 다르게 index가 아닌 reference 구조로 동작해 중간의 공간을 만들어 낼 수 있음.
• ==와 is 차이를 구분해야 함.
  == : 값의 일치를 확인함. (values are equivalent)
  is : 두 object의 reference link를 확인함. 같은 곳에 저장되어있는가 (values are stored at the same place)

2. Basic Structure : Singly linked list

• Singly linked list는 node와 reference로 구성되어있다.
• A node : 
  - variable : next node에 대한 reference. (이 node의 다음 node는 무엇인가 reference 구조를 저장) 
  - variable : value object를 저장하고 있는 reference를 저장.
• Special nodes : Head and Tail (있으면 매우 유용하다.)
  - Head : list의 맨 처음 node. 이 Head의 다음 node는 값이 들어있는 node가 될 것. 
  - Tail : 이것의 다음 node는 존재하지 않음. 
• 아래 그림 상의 하나의 네모 박스가 node가 됨. node 안에는 object를 가리키는 variable과 next를 가리키는 variable이 존재함. 첫 박스는 Head이기 때문에 next는 바로 다음 값이 들어있는 첫번째가 될 것임. object는 Head라는 special node이기 때문에 따로 값이 존재하지 않음.

• 만약 node의 reference가 바뀌었다 하면 기존의 next가 아닌 다른 값을 가리킬 수 있을 것. 즉 사이의 공간을 만들어 낼 수 있는 구조가 된다.

3. Implementation of Node class

• next noded의 reference / value object를 가리키는 reference variable
• association relationship - 1 to 1. 한 node는 next node만을 가질 수 있다. (하나의 node - 하나의 next node만을 가짐)

UML Notation of class Node()

class Node():
  nodeNext = '' 
  objValue = ''
  binHead = False
  binTail = False
  
  def __init__(self, objValue='', nodeNext='', binHead=False, binTail=False):
    self.nodeNext = nodeNext
    self.objValue = objValue
    self.binHead = binHead
    self.binTail = binTail

  def getValue(self):
    return self.objValue

  def setValue(self, objValue):
    self.objValue = objValue

  def getNext(self):
    return self.nodeNext

  def setNext(self, nodeNext):
    self.nodeNext = nodeNext

  def isHead(self):
    return self.binHead
    
  def isTail(self):
    return self.binTail

node1 = Node(objValue = 'a')
nodeTail = Node(binTail=True)
nodeHead = Node(binHead=True, nodeNext = node1)

print(node1.getValue())