링크드 리스트

각 노드가 데이터와 포인터를 가지고 한 줄로 연결이 되어 있는 방식으로 데이터를 저장하는 자료 구조 이다.
노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

이런식으로 연결이 가능하다.

무작위로 저장이 되어 있는 데이터의 형식에 next에 다음으로 올 데이터를 가리키게 함으로서 링크로 연결한 배열을 말한다.

data - 저장하고 싶은 정보
next - 다음 노드에 대한 reference

node1.next = node2 (node1.next는 node2의 참조이다.)

head : 링크드 리스트의 시작지점
tail : 링크드 리스트의 끝지점

노드 만들어 주기

노드를 만들어 주는 클래스로 데이터가 들어갈 자리인 data와 포인터가 가리킬 노드가 들어갈 next 를 만들어 준다.
(현재는 다음에 있는 노드가 없기 때문에 None)

링크드 리스트 만들어 주기

head 노드에는 현재 없기 때문에 None, tail노드에도 없기때문에 None으로 만들어 준다.

str을 사용해서 print를 해줄 데이터의 형태를 정의해 줬다. 각 노드별로 '|'를 사용해서 분리 해줬다.

그리고 iterator = self.head 첫 head노드를 정의를 해 준 뒤
iterator가 None이 아닐 경우 res_str 문자열에 더해준다.

'|2|3|5|7|' 링크드 리스트가 나온다.

링크드 리스트의 접근

배열 접근은 특정위치에 저장된 데이터에 바로 접근이 가능하지만 링크드 리스트는 포인터로 연결되었기 때문에 head 부터 순차적으로 원하는 값으로 접근해야 한다.

def find_node_at(self, index):
"""링크드 리스트 접근 연산, 파라미터에 있는 인덱스는 항상 있다고 가정"""
  iterater = self.head
  for _ in range(index):
     iterater  = iterater
  return iterator

시간복잡도

배열에서 접근 하는 것 만큼 효과적이지 않다.
인덱스x에 있는 노드에 접근하기 위해서 head에서 다음 노드로 x번 가면 된다.

링크드 리스트의 추가 연산(append)

추가 연산을 할 때 생각해야 한다.

• 링크드 리스트가 비어 있을때
• 그냥 맨 뒤에 추가 할 때

def append(self, data):
    """링크드 리스트 추가 연산 메소드"""
    # 삽입하고자 하는 데이터를 Node화 시겨준 다음
    new_node = Node(data)
    
    if self.head is None:
      self.head = new_node    # 추가된 노드가 head 이자 tail
      self.tail = new_node
    
    # 기존에 노드가 있을 경우
    else:
      self.tail.next = new_node    # 포인터를 설정 tail노드의 next를 new_node로 설정 
      self.tail = new_node         # new node를 다시 tail로 설정 
      

추가 연산은
경우 1 : 링크드 리스트가 비어 있을때
경우 2 : 기존에 노드가 있을 경우에 추가하는 경우
를 생각하면 된다.

링크드 리스트 삽입연산(insert)

추가연산은 맨 끝에 추가되는 것과는 다르게 노드 중간에도 추가를 할 수 있기 때문에 삽입 하고자 하는 데이터를 이전 노드에서 그 뒤에 추가 하는 방식으로 접근 해야 한다.
경우1 삽입하는 위치가 tail 노드 뒤인 맨 끝인 경우
경우2 삽입하는 위치가 노드 중간에 삽입하는 경우

def insert_after(self, prvious_node, data):
    """링크드 리스트 삽입연산 메소드 """
    new_node = Node(data)
    
    # previous_node가 tail 노드 뒤에 삽입 하는 경우
    if prvious_node = self.tail:
       self.tail.next = new_node
       self.tail = new_node
    # 삽입 하는 위치가 특정 노드 뒤 인 경우
    else:
       new_node.next = previous_node.next  # 새로운 노드의 next가 prvious_node의 next
       previoust_node.next = new_node      # previouse_node의 next를 new node로 지정

새로운 노드가 맨 앞에 삽입 연산 인경우

경우1 head 노드가 없는 경우
경우2 head 노드가 있는 경우

def prepand(self, data):
   new_node = Node(data)
   
   # head 노드가 없는 경우
   if self.head is None:
     self.head = New_node
     self.tail = New_node
  # head 노드가 현재 존재하는 경우
  else:
     new_node.next = self.head
     self.head = new_node

삭제 연산

삭제하려는 노드가 tail노드 인지 아닌지만 생각을 해주면 된다.
경우 1 삭제하려는 node가 tail 노드 인지
경우 2 삭제하려는 node가 tail 노드가 아닌 경우

삭제 연산을 하는 경우 지워주는 노드를 return 해주는 것이 관례

def delete_after(self, prvious_node):
  data = previous_node.next.data  # 삭제하고자 하는 노드를 data로 가리켜 준다.
  
  # 삭제하려는 노드가 previous node 인 경우
  if previous_node is self.tail:
    previous_node = None
  # 아닌 경우
  else:
    previous_node.next = previous_node.next.next
  
  return data

링크드 리스트 연산에서 링크를 끊어서 데이터를 찾을 수 없는 상태가 되면 삭제를 했다고 판단한다.

가장 앞에 있는 데이터 삭제

주어진 노드의 다음 노드를 삭제하는 방식을 고수하기 때문에 head 노드를 삭제할 수 없다.

지우려는 노드가 리스트에서 마지막 남은 노드 일때를 생각해서 지워야 한다.

def popleft(self):
   """링크드 리스트의 가장 앞 노드를 삭제하는 경우 단, 리스트에 항상노드가 있다고 가정"""
   data = self.head.data    # 맨 앞 노드의 data를 담아준다.
   
   # 마지막 남은 노드인경우
   if self.tail is self.head:
     self.head = None
     self.tail = None
   # 아닌경우
   else:
     self.head = self.head.next
   
   return data

링크드 리스트 시간 복잡도

접근

링크드 리스트에서 data에 접근 연산의 시간 복잡도는 노드와 노드 사이를 포인터로 연결을 해 놓은 상태이기 때문에 한 번에 접근 할 수 없습니다.

그래서 최대 n 번 할 수 있기 때문에 시간 복잡도는 O(n) 이다.

탐색

배열의 탐색과 똑같다 O(n)이다.

삽입과 삭제

삽입과 삭제는 삽입하려고하는 노드 혹은 제거하고자 하는 그 이전의 node만을 건들기 때문에 어떠한 상황에서도 똑같은 순번이 필요한다. 그래서 O(1)이다.

현실적인 경우

삽입과 삭제 그 자체만으로 생각을 해봤을때는 O(1)이지만 삽입 위치를 찾는 다거나, 삭제노드 그 이전의 노드를 찾는 탐색 시간 복잡도는 O(n)이기 때문에 O(n+ 1)= O(n)이 된다.

특수 상황

만약 맨 앞의 위치에 삽입, 삭제 tail 노드를 삭제 삽입을 해주게 될 경우 따로 탐색이 필요가 없다. head 노드와 tail노드에서 바로 접근이 가능하기 때문이다. 그래서 O(1)+ O(1) 이므로 O(1)이다.

하지만 맨 끝에 삭제를 위해서는 Previous node를 탐색해야 하는 경우가 필수적으로 필요하기 때문에 O(n)이 된다.

따라서 head 노드의 삽입, 삭제, tail 노드의 삽입의 경우에는 다른 경우와 다른 특수상황이라고 여기며 이때의 시간 복잡도는 O(1)이다.

---

출처 : 코드잇 자료구조