[1주차 - Day01] 어서와! 자료구조와 알고리즘은 처음이지?(1-2)

7~9. 연결 리스트

---

추상적 자료구조(Abstract Data Structures)

• Data
  ex) 정수, 문자열, 레코드 ...
• A set of operations
  삽입, 삭제, 순회 ....
  정렬, 탐색 ...

기본적 연결 리스트

여러 Node로 구성되어 있으며, Node는 Data와 Link(next)로 구성되어있음

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

class LinkedList:
  def init(self):
  self.node_count = 0
  self.head = None
  self.tail = None

 

단방향 연결 리스트 연산

1. 특정 원소 참조(k번째)

def getAt(self, pos):
  if pos < 0 or pos > self.nodeCount:
  	return None

  i = 0
  curr = self.head
  while i < pos:
    curr = curr.next
    i += 1

  return curr

 

2. 연결리스트 순회

def traverse(self):
  result = []
  curr = self.head
  while curr.next:
    curr = curr.next
    result.append(curr.data)
    
  return result

 

3. 원소의 삽입

주의사항

1. 삽입하려는 위치가 리스트 맨 앞일때
   • prev 없음
   • Head 조정 필요
2. 삽입하려는 위치가 리스트 맨 끝일 때
   • Tail 조정 필요

def insert_at(self, pos, new_node):
    if pos < 1 or pos > self.node_count + 1:
        return False

    if pos == 1:
        new_node.next = self.head
        self.head = new_node

    else:
        if pos == self.node_count + 1:
            prev = self.tail
        else:
            prev = self.get_at(pos - 1)
        new_node.next = prev.next
        prev.next = new_node

    if pos == self.node_count + 1:
        self.tail = new_node

    self.node_count += 1
    return True

 

4. 원소 삭제

def pop_at(self, pos):
        if pos < 1 or pos > self.node_count:
            raise IndexError

        prev_node = None
        if pos == 1:
            popped_node = self.head
            self.head = popped_node.next
        elif pos <= self.node_count:
            prev_node = self.get_at(pos - 1)
            popped_node = prev_node.next
            prev_node.next = popped_node.next

        if pos == self.node_count:
            self.tail = prev_node

        self.node_count -= 1
        return popped_node.data

 

---

맨 앞에 dummy node를 추가한 연결 리스트

특정 원소의 바로 다음을 지정하여 원소를 삽입/삭제하는 연산을 정의하기 위해 맨 앞에 dummy node를 추가한다.

더미노드(dummy node) : 데이터 원소를 담고 있지 않은 노드

head와 tail을 더미 노드로 구현하면 좀더 깔끔하게 작성할 수 있다.

 

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


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

	# 리스트 순회
    def traverse(self):
        result = []
        curr = self.head
        while curr.next:
            curr = curr.next
            result.append(curr.data)
        return result

	# 특정 원소 참조(k 번째)
    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr

	# 원소 삽입(Node를 참조)
    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

	# 원소 삽입(위치 index를 참조)
    def insertAt(self, pos, newNode):
        if pos < 1 or 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)

	# 원소 삭제 (Node를 참조)
    def popAfter(self, prev):
        if prev.next == None:
            return None
        
        cur = prev.next
        prev.next = cur.next
        if cur.next == None:
            self.tail = prev
        self.nodeCount -= 1
        
        return cur.data

	# 원소 삭제(위치 index 참조)
    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        prev = self.getAt(pos -1)
        return self.popAfter(prev)
        
        
    # 두 리스트 합치기
	def concatenation(self, L):
    	self.tail.next = L.head.next
        if L.tail:
        	self.tail = L.tail
        self.nodeCount += L.nodeCount


def solution(x):
    return 0

 

 

10. 양방향 연결 리스트

---

양방향 연결 리스트(Doubly Linked Lists)

한 쪽으로만 링크를 연결하지 말고, 양쪽으로!
-> 앞으로도(다음 노드) 뒤로도(이전 노드)진행 가능

 

• Node의 구조 확장

class Node:
  def __init__(self, item):
      self.data = item
      self.prev = None#prev링크를 따라갈 수 있도록 링크도 None으로 초기화!
      self.next = None

 

• 리스트 처음과 끝에 dummy node를 두자! -> 데이터를 담고 있는 node들은 모두 같은 모양이 된다.

class DoublyLinkedList:
  def __init__(self, item):
      self.nodeCount = 0
      self.head = Node(None)#더미노드
      self.tail = Node(None)#더미노드
      self.head.prev = None
      self.head.next = self.tail#헤드와 테일이 서로를 가리키고 있음
      self.tail.prev = self.head
      self.tail.next = None

 

1. 리스트 순회

# 정방향 순회
def traverse(self):
  result = []
  curr = self.head
  while curr.next.next:
    curr = curr.next
    result.append(curr.data)
  return result


# 역방향 순회
def reverse(self):
  result = []
  cur = self.tail
  while cur.prev.prev:
    cur = cur.prev
    result.append(cur.data)
  return result

 

2. 원소 삽입

# 원소 이전에 삽입
def insertAfter(self, prev, newNode):
  next = prev.next
  newNode.prev = prev
  newNode.next = next
  prev.next = newNode
  next.prev = newNode
  self.nodeCount += 1
  return True


# 원소 이후에 삽입
def insertBefore(self, next, newNode):
  newNode.next = next
  newNode.prev = next.prev

  next.prev.next = newNode
  next.prev = newNode

  self.nodeCount += 1
  return True


def insertAt(self, pos, newNode):
  if pos < 1 or pos > self.nodeCount + 1:
  	return False

  prev = self.getAt(pos - 1)
  return self.insertAfter(prev, newNode)

 

3. 원소 삭제

# 원소 이전 노드를 참조하여 현재 노드 삭제
def popAfter(self, prev):
  cur = prev.next
  prev.next = cur.next
  cur.next.prev = prev
  self.nodeCount -= 1
  return cur.data


# 원소 이후 노드를 참조하여 현재 노드 삭제
def popBefore(self, next):
  cur = next.prev
  cur.prev.next = next
  next.prev = cur.prev
  self.nodeCount -= 1
  return cur.data


def popAt(self, pos):
  if pos < 1 or pos > self.nodeCount:
  	raise IndexError

  prev = self.getAt(pos -1)     
  return self.popAfter(prev)

 

4. 리스트 병합

def concat(self, L):
  prev = self.tail.prev
  prev.next = L.head.next
  L.head.next.prev = prev
  self.tail = L.tail
  self.nodeCount += L.nodeCount

 

11. 스택

---

후입선출(LIFO) 구조

스택은 선형 배열과 연결 리스트 두 가지를 이용해서 구현할 수 있다.

스택 연산

• size() : 현재 스택에 들어 있는 데이터 원소의 수를 구함
• is_empty() : 현재 스택이 비어 있는지를 판단
• push(x) : 원소 x를 스택에 추가
• pop() : 스택에 가장 나중에 저장된 데이터 원소를 제거하고 반환
• peek() : 스택에 가장 나중에 저장된 데이터 원소를 반환

class ArrayStack:
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def is_empty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

class LinkedListStack:
    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.get_length()

    def is_empty(self):
        return self.size() == 0

    def push(self, item):
        node = Node(item)
        self.data.insert_at(self.size() + 1, node)

    def pop(self):
        return self.data.pop_at(self.size())

    def peek(self):
        return self.data.get_at(self.size()).data