연결 리스트

노드 : 각각의 소세지

저장할 데이터와 다음 노드로의 연결을 포함하고 있다.

단순연결리스트 : 한방향으로 연결된것
이중연결리스트 : 양방향
원형연결리스트 : 가장뒤의 노드가 맨앞의노드에 연결되어 있다.

배열과의 차이점

배열: 인덱스를이용해 데이터에 접근할수있다.

연결리스트는 현재노드에서 연결된노드로만 접근할수있다. 인덱스가 없다.

연결리스트가 시작하는곳 head

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

    def __str__(self):
        return str(self.val)

print에서 출력할때 str으로 변환해서 출력하는데 객체같은경우는 불가능하기때문에 str메소드를 지정했다.

연결리스트 - 왜알아야 하는가?

면접문제에 나온다!

그냥 대놓고 연결리스트를 언급하고 문제가 나온다. 마치 배민문제처럼..

효율성

효율성이 되게 없어보이는데;

트리, Database등 더 고차원 구조의 기반이 된다.

시간복잡도

중간걸 삭제하고 앞에것을 뒤랑 연결한다.

어레이는 중간에 추가하거나 삭제를하면 나머지 전체를 옮겨줘야하기 때문에 시간복잡도가 쫌 문제인데 O(N) 연결리스트는 그렇지 않다.

연결리스트에서 노드 삭제하기

# 연결 리스트의 노드. 단일 연결 리스트의 경우입니다.
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

    def __str__(self):
        return str(self.val)

# 연결 리스트 클래스. head 와 tail을 가지고 있으며, 가장 뒤에 새로운 노드를 추가하는 addToEnd 함수가 있습니다.
class LinkedList:
    def __init__(self, head):
        self.head = head
        self.tail = head

    def addToEnd(self, node):
        self.tail.next = node
        self.tail = node

    def __str__(self):
        node = self.head
        toPrint = []
        while node:
            toPrint.append(str(node.val))
            node = node.next
        return "->".join(toPrint)

# 주어진 배열을 linkedlist로 변환해서 돌려줍니다. 실습 3-1을 참조하세요
def toLinkedList(lst):
    ll = LinkedList(Node(lst[0]))
    for i in range(1, len(lst)):
        ll.addToEnd(Node(lst[i]))

    return ll

####################################################################################################################################

def deleteNode(ll, valToDelete):
    if ll.head.val == valToDelete:
        ll.head = ll.head.next

    currNode = ll.head
    nextNode = currNode.next

    while nextNode:    
        if nextNode.val == valToDelete:
            currNode.next = nextNode.next #nextNode.next 는 nextNode와 같다.
            if ll.tail == nextNode: #그래서 tail인지 확인하고, nextNode의 바로전Node로 대체한다.
                ll.tail = currNode
            break

        #노드이동.            
        currNode = currNode.next  
        nextNode = currNode.next  

def main():
    nums = [2,8,19,37,4,5]
    ll = toLinkedList(nums)
    print(ll)
    deleteNode(ll, 19)
    print(ll) # 19를 삭제하였으므로, 2->8->37->4->5
    deleteNode(ll, 3)
    print(ll) # 3이 없으므로, 2->8->37->4->5

내가만든 연결리스트

#민우코드

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

  def __str__(self):
    return str(self.val)

class LList:
  def __init__(self, head):
    self.head = head
    self.tail = head

  def addToEnd(self, node):
    #add이전에 마지막노드(tail)을 새로넣는 노드의 이전노드로 지정.
    node.before = self.tail
    self.tail.next = node
    self.tail = node


  def __str__(self):
    node = self.head
    toPrint = []
    while node:
      toPrint.append(str(node.val))
      node = node.next
    return "->".join(toPrint)

  def find(self, valToFind):
    node = self.head
    while node:
      if node.val == valToFind:
        return node
      else:
        if node.next == None:
          return None
        node = node.next


  def deleteNode(self, valToDelete):
    node = self.find(valToDelete)
    if node:
      if self.head == node:
        self.head = self.head.next
      elif self.tail == node:
        #tail의 바로전노드의 next 프로퍼티를 tail.next(None)으로 바꾼다.
        self.tail.before.next = self.tail.next
        #tail을 기존tail의 바로전 노드로 바꾼다.
        self.tail = self.tail.before
      else:
        node.before.next = node.next
        node.next.before = node.before

    else:
      return None




ll = LList(Node(3))
ll.addToEnd(Node(4))
ll.addToEnd(Node(8))
print(ll.tail.before)
print(ll)
print(ll.deleteNode(8))
print(ll)

기출문제

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

class LL():
  def __init__(self, node):
    self.root = node
    self.tail = node

  def addToEnd(self, node):
    if self.tail.val == self.root.val and self.root.next is None:
      self.root.next = node
    else:
      self.tail.next = node
      self.tail = node

def arrayToLL(array):
  ll = LL(Node(array[0]))

  while ll.tail.val is not -1:
    ll.addToEnd(Node(array[ll.tail.val]))

  return ll

arr = [1,4,-1,3,2]
ll = arrayToLL(arr)

print(ll.root.val)
print(ll.root.next.val)
print(ll.root.next.next.val)
print(ll.root.next.next.next.val)
# print(ll.root.next.next.next.next.val) #None

Linked List