연결리스트의 특징과 파이썬 코드 구현

Linked List

연결리스트는 대표적은 추상적 자료구조의 한 예로 기존 리스트 자료구조와 달리 Node와 Link를 가진 자료구조이다.

 

위에 그림처럼 데이터를 담고 있는 Node 그리고 각 노드들은 연결하는 Link를 통해 이루어져 있다.

연결 리스트의 장단점

연결리스트의 경우 링크를 통해 각 데이터가 연결이 되어 있기 때문에 배열에 비해 추가 / 삭제가 용이한 점을 가지고 있다.

반면에 특정 데이터를 찾기 위한 순차 탐색에 있어 탐색 속도가 배열에 비해 느린 단점을 가지고 있다.

하지만 연결 리스트는 '동적 할당'을 기반으로 한 자료구조이기 때문에 크기를 미리 지정할 필요가 없다는 큰 장점을 가지고 있기 때문에 많이 사용되어 진다.

그래서 궁극적으로 내가 어떠한 목적을 가지고 코드를 구성하느냐에 따라 배열과 연결리스트의 장단점을 고려해서 사용해야 한다.

연결 리스트 구현

 

노드 객체

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

앞서 말했듯이 노드는 데이터와 노드를 연결하는 링크로 구성되어 있기 때문에 객체 생성시 self.data, self.next로 구성한다.

연결리스트 객체

class LinkedList: 
	''' Node class을 통해 연결하고 구성된다. ''' 
    
    def __init__(self): 
    	self.nodeCount = 0 
        self.head = None 
        self.tail = None

그리고 연결리스트의 객체룰 생성하는 경우에는 총 노드의 개수 = 0, 맨 앞의 노드, 맨 뒤의 노드에 대해 None 값을 생성해 객체를 만들어 준다.

연결리스트 메소드

이제 노드와 연결 리스트의 객체를 생성했으니 연결리스트가 가지는 메소드들에 대해 구성을 할 차례이다

1. traversal() - list traversal
2. getAt(pos) - certain element reference
3. getLenth() - get lenth
4. insert(pos, newNode) - insert element
5. popAt(pos) - delete element
6. merge(L) - merge list to list

위와 같이 연결리스트의 메소드는 총 6가지로 이루어져 있다.

특정 위치 노드 찾기.

getAt method의 경우 특정 위치를 인자로 받아 그 노드를 찾아 반환하는 메소드이며 구현한 코드는 다음과 같다.

def getAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        return None
    curr = self.head
    i = 1
    while i < pos:
        curr = curr.next
        i += 1
    return curr

 

노드 삽입

연결리스트의 경우 배열처럼 데이터를 삽입 하는 메소드를 구현할 수 있는데 기존 배열과는 달리 연결리스트의 경우 링크를 연결해 노드를 삽입하기 때문에 알고리즘 설계는 다음과 같다.

 

1. newNode 를 삽입
2. 성공/실패에 따라 true/false 를 리턴.

주의사항

1. 삽입하려는 위치가 리스트 맨앞일때 -> prev 없음, head 조정 필요

2. 삽입하려는 위치카 리스트 맨 끝일때 -> prev = tail

3. 빈리스트의 삽입할 경우. → 1) 조건을 잘 활용하여 tail 조정.

def insert(self, pos, newNode):
    if pos < 1 and pos > self.nodeCount + 1:
        return False
 
    if pos == 1:
        newNode.next = self.head.next
        self.head = newNode
    else:
        if pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        newNode.next = prev.next
        prev.next = newNode
 
    if pos == self.nodeCount + 1:
        newNode = self.tail
 
    self.nodeCount += 1
    return True

노드 삭제.

노드 삭제의 경우도 앞서 한 노드의 삽입의 경우와 마찬가지로 설계시 몇가지 고려할 사항이 있다.

1. node를 삭제
2. node의 데이터를 리턴.

주의사항.

1. 삭제하려는 node가 맨앞의 것일때 -> prev 없음, head 조정

2. 리스트 맨 끝의 node를 삭제할 때 -> tail 조정 필요.

3. 유일한 노드를 삭제할때 -> 위 조건 만으로 만족 하는가?

 def popAt(self, pos):
      data = 0
      if pos < 1 and pos > self.nodeCount:
          raise IndexError('index out of range')
 
      if pos == 1:
          data = self.head.data
          self.head = self.head.next
      else:
          prev = self.getAt(pos - 1)
          curr = prev.next
          data = curr.data
          if pos == self.nodeCount:
              prev.next = None
              self.tail = prev
          else:
              prev.next = curr.next
 
      if pos == self.nodeCount:
          self.head = None
          self.tail = None
 
      self.nodeCount -= 1
      return data

노드 순회 및 길이, 노드 병합 메소드

def traversal(self):
    result = []
    curr = self.head
    while curr:
        result += [curr.data]
        curr = curr.next
    return result
    
def getLenth(self):
    return self.nodeCount
 
def concat(self, L):
    self.tail.next = L.head
    if L.tail:
        self.tail = L.tail
 
    self.nodeCount += L.nodeCount

 

Dummy Linked List

 

Dummy Linked List는 기존 리스트와 달리 앞에 빈 Dummy 노드를 추가해 구현한 연결리스트 이다.

연결리스느의 가장 큰 장점은 앞서 말했듯이 원소의 삽입/ 삭제가 용이하다는 점이다.

 

리스트를 따라서 하나 하나 원소들을 대상으로 어떤 작업을 하다가, 그 위치에 새로운 데이터 원소를 삽입하거나, 아니면 그 위치에 있는 데이터 원소를 삭제하는 경우입니다. 앞선 연결리스트에서는 프로그래밍 연습을 쉽게 하기 위해서 특정 번째 를 지정하여 원소를 삽입/삭제하는 연산을 정의하고 코딩으로 구현하였는데, 이번에는 Dummy Linked List를 통해 특정 원소의 바로 다음 을 지정하여 원소를 삽입/삭제하는 연산을 정의하고 구현하면 보다 나은 코드가 될 것이다.

그러나 맨 앞에 원소를 추가 (삽입) 하거나 맨 앞의 원소를 제거 (삭제) 하는 연산을 지정하기가 좀 애매한데 이런 경우에도 동일한 방법을 적용하기 위해서, 이번에는 연결 리스트의 맨 앞에다가 데이터 원소를 담고 있지 않은, 그냥 자리만 차지하는 노드를 추가한, 더비 연결 리스트를 정의한 것이다.

 

코드 구현

---

class Node:
    
    def __init__(self, item):
		self.data = item
		self.next = None
    
 
 
class DummyLinkedList:
 
    def __init__(self):
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail
        self.nodeCount = 0
 
    def getAt(self, pos):
        if pos < 1 and pos > self.nodeCount:
            return None
        
        curr = self.head
        i = 0
        while i < pos:
            curr = curr.next
            i += 1
 
        return curr
 
    def getLenth(self):
        return self.nodeCount
 
    def traversal(self):
        result = []
        curr = self.head
 
        while curr.next:
            result += [curr.data]
            curr = curr.next
            
 
        return result
    
    def concat(self, L):
        self.tail.next = L.head
        if L.tail:
            L.tail = self.tail
        self.nodeCount += L.nodeCount
 
    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
 
        if prev.next is None:
            self.tail = newNode    
        prev.next = newNode
 
        self.nodeCount += 1
        return True
 
    def insertAt(self, pos, newNode):
        if pos < 1 and pos > self.nodeCount + 1:
            return False
        
        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
 
        return self.insertAfter(prev, newNode)
 
 
    def popAfter(self, prev):
        curr = prev.next
 
        if self.nodeCount == 1:
            self.head.next = None
            self.tail = None
        else:
            if curr is None:
                prev.next = None
                self.tail = prev
            else:
                prev.next = curr.next
        
        self.nodeCount -= 1
 
        return curr.data
 
    def popAt(self, pos):
        if pos < 1 and self.nodeCount < pos:
            raise IndexError('out of index')
 
        prev = self.getAt(pos - 1)
 
        return self.popAfter(prev)