🚶‍♂️Road to 코테(3) - 연결리스트

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬 편

연결리스트

원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조.

성질

• k번째 원소를 확인/변경하기 위해 O(k)가 필요
  -> 공간에 원소가 연속해서 위치하지 않기 때문에.
• 임의의 위치에 원소를 추가/임의 위치 원소 제거는 O(1)
• 원소들이 메모리 상에 연속해있지 않지만 할당이 쉽다.

종류

배열과 연결리스트

메모리 상에 원소를 놓는 방법은 달라도 원소 사이의 선후 관계로 일대일 정의가 된다. 배열과 연결리스트는 둘 다 선형 자료구조이다. 배열은 배치가 연속이지만 연결 리스트는 불연속이다. 원소가 다음 원소 or 이전,다음 원소의 주소값을 가지고 있어야 하므로 메모리가 좀 더 필요.

연결리스트에서는 임의의 위치에 있는 원소로 가기 위해서 순차적으로 방문해야 한다. 우리는 첫 원소의 주소만 알고 있기 때문에.
추가하고 싶은 위치의 주소를 알고 있을 경우에만 O(1)이다.
임의 위치의 원소를 제거하는 연산은 O(1)에 가능하다. 지우려는 원소의 이전 원소에게 지우려는 원소 이후의 원소 주소를 알려주면 된다.

메모장과 텍스트 에디터같은 상황에서 연결리스트를 쓰게 된다.
-> 임의의 위치에 원소를 추가하거나 임의 위치의 원소를 제거하는 연산을 많이 해야하면 고려.

구현

Node 구조체나 클래스를 만들어서 원소 생성마다 동적 할당을 하는 방식으로 구현하는 것이 일반적이다.

1	class Node:
2	    def __init__(self, data):
3	        self.data = data  #data는 값을 가리키는 변수(속성, attribute)
4	        self.next = None  #next는 다음 노드를 가리키는 변수
5	
6	
7	head=Node(1) # 맨 첫 번째 노드는 head라고 하자
8	head.next=Node(2)
9	head.next.next=Node(3)

가장 처음

맨 마지막에 last라는 데이터를 가진 노드를 만들어보자.

node = head
while node.next:  # 현재 노드의 next가 None이 아닐 동안 실행
    node = node.next
node.next = Node('last')

연결리스트를 class로 구현해보자.

class LinkedList:
    def __init__(self):
        self.head = None
        self.length = 0

    def __len__(self):
        return self.length

구현할 단일 연결 리스트의 메서드는 아래와 같다. 이름은 리스트와 데크(deque)의 메서드 이름을 참조했다.

• appendleft(x): 연결 리스트의 처음에 x를 추가한다.
• append(x): 연결 리스트의 끝 x를 추가한다.
• remove(): 연결 리스트에서 마지막 노드의 값을 반환하고, 노드는 삭제한다.
• insert(i, x): 연결 리스트의 i번 인덱스에 x를 추가한다.
• reverse(): 연결 리스트를 제자리에서 순서를 뒤집는다.

가장 기본적인 append 메소드와 그에 반대되는 appendleft 메소드를 만들어보면

class LinkedList:
    def __init__(self):
        self.head = None
        self.length = 0

    def __len__(self):
        return self.length
        
    def append(self,data):
      if self.head is None:
        self.head=Node(data)
      else:
        node=self.head #첫번째 노드를 불러오기
        while node.next:
          node=node.next
        node.next=Node(data)
      self.length+=1
    
    def appendleft(self,data):
      if self.head is None:
        self.head = Node(data)
      else:
        node=Node(data)
        node.next=self.head
        self.head=node
      self.length+=1
    

appendleft는 왼쪽부터 추가되고 append는 오른쪽에서부터 추가된다.
다음으로 구현할 메소드는 상태 출력과 값 검색이다.

def __str__(self):
  
  if self.head is None:  #없으면 없다고 말하고
    return "Empty LinkedList"        
  print("List Print")
  node=self.head  #첫 노드를 가져온 다음에
  res="Head"
  while node:   # 노드 안에 값이 있으면
    res+="-> "+str(node.data)  #출력에 포함
    node=node.next           
  return res

def __contains__(self,target):
  if self.head is None:
    return False
  node=self.head
  while node:
    if node.data==target:   #있으면 출력
      return True
    node=node.next
  return False
      

마지막으로 remove()과 insert(i,x)를 구현해보겠다.

remove 메소드를 설명하자면.
임시 노드 두 개(node,prev)를 만드는 것이 포인트이다.
1. node는 삭제할 원소를 찾고,prev가 뒤를 따라간다.
2. 삭제할 원소를 찾았으면 prev.next가 node가 아닌 node.next가 되게한다.
-> 삭제할 원소가 head 일때와 아닐 때를 구분한다.

def remove(self,target):
  node=self.head
  while node is not None and node.data != target:
    prev=node
    node=node.next
  if node is None:
    return False
  if node==self.head:
    self.head=self.head.next
  else:
    prev.next=node.next
  self.length-=1
  return True
  

insert() 메소드는 몇가지 규칙이 필요하다.
노드 삽입시 처리할 단계도 많고 범위를 벗어날 시에 어떻게 처리할 것인지도 고려해야 한다.

• 0보다 작은 인덱스 시 head에 노드를 삽입한다.
• 인덱스가 length보다 크면 가장 끝에 삽입한다.

1. 임시 노드를 만들고 삽입 위치까지 이동한다.
2. 삽입할 노드를 생성한다.
3. 새 노드의 next가 임시 노드의 다음 노드를 가리키게 한다.
4. 임시 노드의 next가 새 노드를 가리키게 한다.

def insert(self,i,data):
  if i<0:
    self.appendleft(data)
  elif i>self.length:
    self.append(data)
  else:
    node=self.head
    for _ in range(i-1):
      node=node.next
    temp=Node(data)
    temp.next=node.next
    node.next=temp
    self.length+=1

연습 문제를 풀어보자

백준 1406번 - 에디터

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

• L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
• D : 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
• B : 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)삭제로 인해 커서는 한칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
• P $ $라는 문자를 커서 왼쪽에 추가함
  초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

연결리스트를 활용하여 파이썬으로 만들었다.

import sys

class Node:
  def __init__(self, data):
    self.data = data  #data는 값을 가리키는 변수(속성, attribute)
    self.next = None  #next는 다음 노드를 가리키는 변수
    
    
class LinkedList:  
  def __init__(self):
    self.head = None
    self.length = 0
    self.cursor=0

  def __len__(self):
    return self.length
    
    
  
  def append(self,data):
    if self.head is None:
      self.head=Node(data)
    else:
      node=self.head
      while node.next is not None:
        node=node.next
      node.next=Node(data)
    self.length+=1
    self.cursor+=1
    
        
  def __str__(self):
    if self.head is None:
      return "It is empty"
    res=""
    node=self.head
    while node is not None:
      res+=str(node.data)
      node=node.next
    return res
      
  def L(self): 
    if self.cursor!=0:
      self.cursor-=1
    
  
  def D(self): 
    if self.cursor!=self.length:
      self.cursor+=1
  
#커서 왼 쪽에 있는 원소를 삭제해야한다. 왼쪽 
  def B(self):   
    if self.cursor!=0:
      cursor=self.cursor
      node=self.head
      for _ in range(cursor-1):
        prev=node
        node=node.next
      if node==self.head:
        self.head=self.head.next
      else:
        prev.next=node.next
      self.cursor-=1
      self.length-=1


    
  def P(self,data):
    cursor=self.cursor
    if cursor==0 and self.head is not None:
      temp=Node(data)
      temp.next=self.head
      self.head=temp
      self.cursor+=1
      self.length+=1
      return 
        
    if self.head:
      node=self.head
      for _ in range(cursor-1):
        node=node.next
      temp=Node(data)
      temp.next=node.next
      node.next=temp
      self.cursor+=1
      self.length+=1
      
    else:
      self.head=Node(data)
      self.cursor+=1
      self.length+=1

    
      
    


str_ex=sys.stdin.readline().strip()
n=int(sys.stdin.readline())


editor=LinkedList()
for i in range(len(str_ex)):
  editor.append(str_ex[i])


for _ in range(n):
  func=sys.stdin.readline().split()
  if func[0]=='P':
    editor.P(func[1])
  elif func[0]=='L':
    editor.L()
  elif func[0]=='D':
    editor.D()
  elif func[0]=='B':
    editor.B()

print(editor)

일단, 배운건 다 사용했지만 자꾸 시간초과가 나와 코드를 수정해야한다.
pop과 append로 스택을 활용해서 작성하라는데?
이건 후에 수정해봐야 겠다.