[알고리즘(3)] Python으로 알아보는 연결리스트(Linked-List)

출처: flacticon

 

 

[알고리즘 포스팅 순서]

1. 시간복잡도

2. 배열

3. 연결리스트

4. 스택

5. 큐

6. 트리

7. 그래프

8. 해쉬테이블

9. 정렬(선택, 버블, 삽입, 퀵, 힙, 병합)

10. 코테 대비 백준 문제 풀이 꿀팁

 

 

오늘 알아볼 자료구조는 연결리스트이다.

[연결리스트란?]

연결 리스트는 사슬처럼 여러 데이터를 연결한 것이다.

연결 리스트는 배열처럼 선형 자료 구조이지만, 연속한 메모리에 값을 저장하는 것은 아니다.

연결 리스트에서는 각각의 데이터(원소)들을 노드라고 부른다.

단일 연결 리스트

이중 연결 리스트

순환 이중 연결 리스트

[특징]

1. 종류로는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly linked list), 순환 이중 연결 리스트(Circular Doubly linked list)가 존재한다.

단일 연결 리스트는 한 방향으로만 연결 및 이동이 가능한 리스트이고

이중 연결 리스트는 양방향으로 연결 및 이동이 가능한 리스트이고

순환 이중 연결 리스트는 이중 연결 리스트에서 머리와 꼬리가 연결되어 있는 리스트이다.

 

2. 머리 노드와 꼬리 노드

연결 리스트는 리스트와 다르게 머리 노드와 꼬리 노드가 있다.

머리 노드는 시작 노드를, 꼬리 노드는 마지막 노드를 의미하며

이 두 노드엔 데이터가 따로 담기지 않고 다음 연결되는 노드의 주소를 참조한다.

 

3. 연결

그렇다면 어떻게 연결하겠다는 것일까?

단일 연결 리스트의 경우에는 self.data와 self.next라는 변수를 이용하여

이중 연결 리스트는 위에서 self.prev라는 변수를 추가해서 사용한다.

더 자세히 알아보기 위해 코드를 살펴보자

 

[코드]

(1) 단일 연결 리스트: 코드로 다음과 같은 기능을 지원하도록 구현하였다.

1. push_back(Data data): 연결 리스트의 tail에 data를 삽입
2. push_front(Data data): 연결 리스트의 head에 data를 삽입
3. insert(Iterator it, Data data): it위치에 data를 삽입
4. insert(Iterator it, Data data[]): it위치에 data들을 삽입
5. front(), back(): 각각은 연결리스트의 head의 값과 tail의 값을 리턴
6. delete(Iterator it): it 위치의 데이터를 삭제
7. delete(Iterator it, Number count): it 위치의 데이터를 count개만큼 삭제
8. size(): 연결리스트에 존재하는 모든 노드의 수 반환

from multipledispatch import dispatch #오버로딩이 안되는 파이썬에 가능하게 만듦

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

class Single_Linked_List:
  def __init__(self):
    self.head = None
    self.size = 0

  def push_back(self, data): # 연결 리스트의 tail에 data 삽입
    node = Node(data)
    if self.head is None:
      self.head = node
    else:
      prev = self.head
      while prev.next:
        prev = prev.next
      prev.next = node
    self.size += 1

  def push_front(self, data): # 연결 리스트의 head에 data 삽입
    node = Node(data)
    if self.head is None:
       self.head = node
    else:
      node.next = self.head
      self.head = node
    self.size += 1

  def insert(self, it, data): # it 위치에 data 삽입
    if (it <= 0):
      self.push_front(data)
    elif (0 < it < self.size):
      prev = self.head
      for i in range(it-1):
        prev = prev.next
      node = Node(data)
      node.next = prev.next
      prev.next = node
      self.size += 1
    else:
      print("인덱스 값이 범위를 벗어났습니다.")

  def insert(self, it, *data): # it 위치들에 data들 삽입 # *은 여러개의 인자값을 받을 수 있도록함
    for i in range(len(data)):
      if (it <= 0):
        self.push_front(data[i])
      elif (0 < it < self.size):
        prev = self.head
        for i in range(it-1):
          prev = prev.next
        node = Node(data[i])
        node.next = prev.next
        prev.next = node
        self.size += 1
      else:
        print("인덱스 값이 범위를 벗어났습니다.")

  @dispatch(int)
  def delete(self, it):# it 위치의 data 삭제
    if (it == 0):
      self.head = self.head.next
      self.size -= 1
    elif ( 1 <= it < self.size):
      prev = self.head
      for i in range(it-1):
        prev = prev.next
      prev.next = prev.next.next
      self.size -= 1
    else:
      print("인덱스 값이 범위를 벗어났습니다.")

  @dispatch(int, int)
  def delete(self, it, count): # it 위치부터 data들 count갯수만큼 삭제
    for i in range(count):
      if (it == 0):
        self.head = self.head.next
        self.size -= 1
      elif ( 1 <= it < self.size):
        prev = self.head
        for i in range(it-1):
          prev = prev.next
        prev.next = prev.next.next
        self.size -= 1
      else:
        print("인덱스 값이 범위를 벗어났습니다.")

  def front(self): # head값 리턴
    return print("head:", self.head.data)

  def back(self): # tail값 리턴
    tail = self.head
    for i in range(self.size-1):
      tail = tail.next
    return print("tail:", tail.data)

  def get_size(self): # 연결된 size 리턴
    return print("size: ", self.size)


## __main__ ##
linklist = Single_Linked_List()
linklist.push_back(3) #추가
linklist.push_front(1) #추가
linklist.get_size() #2
linklist.insert(1, 2) #추가
linklist.push_front(0) #추가
linklist.push_back(7) #추가
linklist.front()
linklist.back()
linklist.get_size() #5
linklist.delete(2) #삭제
linklist.delete(0, 2) #삭제
linklist.front()
linklist.back()
linklist.get_size() #2
linklist.insert(0, 1, 2, 3, 4, 5, 6) #추가*6
linklist.front()
linklist.back()
linklist.get_size() #8

-> main문을 실행하면 다음과 같은 결과가 나온다.

 

(2) 이중 연결 리스트: 위와 동일한 기능을 지원하도록 구현하였다.

1. push_back(Data data): 연결 리스트의 tail에 data를 삽입합니다.
2. push_front(Data data): 연결 리스트의 head에 data를 삽입합니다.
3. insert(Iterator it, Data data): it위치에 data를 삽입합니다.
4. insert(Iterator it, Data data[]): it위치에 data들을 삽입합니다.
5. front(), back(): 각각은 연결리스트의 head의 값과, tail의 값을 리턴합니다.
6. delete(Iterator it): it 위치의 데이터를 삭제합니다.
7. delete(Iterator it, Number count): it 위치의 데이터를 count개만큼 삭제합니다.
8. size(): 연결리스트에 존재하는 모든 노드의 수를 구합니다.

from multipledispatch import dispatch #오버로딩이 안되는 파이썬에 가능하게 만듦

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

class Double_Linked_List2(object):
  def __init__(self):
    self.head = Node(None)
    self.tail = Node(None, self.head)
    self.head.next = self.tail
    self.size = 0

  def selectNode(self, idx): # idx에 따른 노드 찾기
    if idx > self.size:
      print("인덱스 값이 범위를 벗어났습니다.")
      return None
    if idx == 0:
      return self.head
    if idx == self.size:
      return self.tail
    if idx <= self.size//2:
      target = self.head
      for _ in range(idx):
          target = target.next
      return target
    else:
      target = self.tail
      for _ in range(self.size - idx):
          target = target.prev
      return target

  def push_back(self, data): # tail에 노드 추가
    if self.size == 0:
      self.head = Node(data)
      self.tail = Node(None, self.head)
      self.head.next = self.tail
    else:
      tmp = self.tail.prev
      newNode = Node(data, tmp, self.tail)
      tmp.next = newNode
      self.tail.prev = newNode
    self.size += 1

  def push_front(self, data): # head에 노드 추가
    if self.size == 0:
      self.head = Node(data)
      self.tail = Node(None, self.head)
      self.head.next = self.tail
    else:
      tmp = self.head
      self.head = Node(data, None, self.head)
      tmp.prev = self.head
    self.size += 1

  def insert(self, idx, data): # idx에 노드 추가
    if self.size == 0:
      self.head = Node(data)
      self.tail = Node(None, self.head)
      self.head.next = self.tail
    else:
      tmp = self.selectNode(idx)
      if tmp == None:
        return
      if tmp == self.head:
        self.push_front(data)
      elif tmp == self.tail:
        self.push_back(data)
      else:
        tmp_prev = tmp.prev
        newNode = Node(data, tmp_prev, tmp)
        tmp_prev.next = newNode
        tmp.prev = newNode
    self.size += 1

  def insert(self, idx, *data): # idx에 노드들 추가
    for i in range(len(data)):
      if self.size == 0:
        self.head = Node(data[i])
        self.tail = Node(None, self.head)
        self.head.next = self.tail
      else:
        tmp = self.selectNode(idx)
        if tmp == None:
            return
        if tmp == self.head:
            self.push_front(data[i])
        elif tmp == self.tail:
            self.push_back(data[i])
        else:
            tmp_prev = tmp.prev
            newNode = Node(data[i], tmp_prev, tmp)
            tmp_prev.next = newNode
            tmp.prev = newNode
      self.size += 1

  @dispatch(int)
  def delete(self, idx): # idx의 노드 삭제
    if self.size == 0:
      print("더이상 삭제할 노드가 없습니다")
      return
    else:
      tmp = self.selectNode(idx)
      if tmp == None:
        return
      elif tmp == self.head:
        tmp = self.head
        self.head = self.head.next
      elif tmp == self.tail:
        tmp = self.tail
        self.tail = self.tail.prev
      else:
        tmp.prev.next = tmp.next
        tmp.next.prev = tmp.prev
      del(tmp)
      self.size -= 1

  @dispatch(int, int)
  def delete(self, idx, count): # idx의 노드 삭제
    for i in range(count):
      if self.size == 0:
        print("더이상 삭제할 노드가 없습니다.")
        return
      else:
        tmp = self.selectNode(idx)
        if tmp == None:
          return
        elif tmp == self.head:
          tmp = self.head
          self.head = self.head.next
        elif tmp == self.tail:
          tmp = self.tail
          self.tail = self.tail.prev
        else:
          tmp.prev.next = tmp.next
          tmp.next.prev = tmp.prev
        del(tmp)
        self.size -= 1

  def front(self): # head값 리턴
    return print("head:", self.head.data)

  def back(self): # tail값 리턴
    return print("tail:", self.tail.prev.data)

  def get_size(self): # size값 리턴
    return print("size: ", self.size)

  def printlist(self): # 전체 list 프린트
    target = self.head
    while target != self.tail:
      if target.next != self.tail:
        print(target.data, '<=> ', end='')
      else:
        print(target.data)
      target = target.next

## __main__ ##
mylist = Double_Linked_List2()
mylist.push_back('A')
mylist.printlist()
mylist.push_back('B')
mylist.printlist()
mylist.push_back('C')
mylist.printlist()
mylist.insert(1, 'D')
mylist.printlist()
mylist.push_front('E')
mylist.printlist()
mylist.get_size()
mylist.delete(0)
mylist.printlist()
mylist.delete(3)
mylist.printlist()
mylist.delete(0)
mylist.printlist()
mylist.insert(1, 'a', 'b', 'c')
mylist.printlist()
mylist.front()
mylist.back()
mylist.get_size()

-> main문을 실행하면 다음과 같은 결과가 나온다.

 

 

끄읏

 

[참고문헌]

1. 위키독스: https://wikidocs.net/224937

2. 블로그(연결 리스트 이론): https://byumm315.tistory.com/entry/%EB%A6%AC%ED%8A%B8%EC%BD%94%EB%93%9C-23-Merge-k-Sorted-Lists

3. 블로그(이중 연결 리스트 코드): https://underflow101.tistory.com/4

4. 동영상(이론, 강추): https://www.youtube.com/watch?v=DzGnME1jIwY&list=PLjSkJdbr_gFZQp0KEoo0Y4KkCI5YqxtjZ&index=2

5. 사진출처: http://wiki.hash.kr/index.php?title=%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8&mobileaction=toggle_view_desktop, https://underflow101.tistory.com/4, https://bigbigpark.github.io/data_structure/linkedlist/