# [알고리즘] 알고리즘의 기초 연결리스트 편

---

📌 본 포스팅은 연결리스트 알고리즘에 대한 내용을 다룹니다.

---

1. 연결리스트와 어레이

• 리스트와 linked list 의 성능 : 값을 꺼내기가 쉽냐, 넣기가 쉽냐, 지우기가 쉽냐로 판단
• 조회관점에서는 리스트가 훨씬 좋다. array[3] 하면 조회가 O(1) 로 끝. linked list는 처음부터 살펴야하기때문에 최악의 경우 처음부터 하나씩 조회하면서 목표 메모리까지 도달 = O(n)
• 리스트는 삽입할때 싹다 한칸씩 옴기고 4번째 메모리에 데이터를 넣어야함.
• 연결리스트는 상자가 다음 상자를 가리키게 만드는 구조라서 가리키는 위치만 바꾸면 됨 삽입에 특화됨.

case	Array	LinkedList
Read	O(1)	O(N)
Insert, Delete	O(N)	O(1)
Append	꽉차면 새 메모리 할당	노드 끝 동적 추가
결론	접근 ->Array	삽입 삭제 -> LinkedList

2. LinkedList 구현

class ListNode: 

    def __init__(self, val = 0, next = None):
        self.val = val
        self.next = next
        F.b(f"   - ⭐️ ListNode({val})실행  : [결과 ({self.val}, {self.next})]")
    def __str__(self):
        return f"({self.val}, {self.next})"

class LinkedList:
    def __init__(self):
        self.head = None
        F.g(f"⭐️ LinkedList() 실행 [head : {self.head}]")

    def append(self,val):
        F.r(f"\n 👉LinkedList.append({val}) 실행 : LinkedList 끝 노드에 {val}을 추가합니다.")
        if not self.head:
            F.y(f"   - 기존 헤드 값 {self.head}. =>  head에  {val} 삽입.")
            self.head = ListNode(val,None)
            # print(f"\t self.head:({self.head.val} , {self.head.next})")
            return 

        node = self.head
        F.y(f"    :: 현재 LinkedList 상태 {node} ::")
        step = 0
        F.g(f"       •STEP({step})-> node.next 없음" if not node.next else "  🔸 insert 위해 끝 node 가기 START")
        while node.next:
            if  node.next:
                F.g(f"      •STEP({step})-> node.next 값{node.next} ")
            node = node.next
            step +=1
        F.y(f"   - 끝노드[{node.val},{node.next}]도착!! 다음 노드에 {val} 추가한 결과↓↓↓↓")
        node.next = ListNode(val,None)

        ## print(ln) 연결 구조 시각화
        result = []
        node = self.head
        while node:
          result.append(str(node.val))
          node = node.next
        F.y(f"     ::APPEND 후 최종 LinkedList 상태 { ' -> '.join(result)}")

    def __str__(self):
        ## print(ln) 연결 구조 시각화
        result = []
        node = self.head
        while node:
          result.append(str(node.val))
          node = node.next
        return " -> ".join(result)

ln =LinkedList()

ln.append(3)
ln.append(5)
ln.append(7)
ln.append(9)

[실행결과]

linked list class 실행결과

• 상자와 화살표를 합쳐서 노드라고 함.
• 노드를 이용해 연결된 녀석.
• 내가가진값 : val
• 상자가 연결하는 화살표 : next
• 값이 안들어올 경우 기본값 0 : val =0
• 화살표 없을경우 next = None
• 첫 요소를 알아야 마지막까지 조회가능 : head = None
• 만약 head 가 아무것도 없으면 하나 만들어줘야한다.
• 제일 헤드에서 테일까지 간다음에 마지막에 붙여준다.
• 노드 = 헤드
• 다음요소가 있으면 계속 노드를 교체한다.
• 마지막 노드에 오면 while 끝나고 다음 노드를 만들어 지목해준다.

출력에 색깔 입히는 F class code

class F:
    ### Functions ### 
    # 기본 세팅
    def colored_text(text, color='default', bold=False):
            '''
            #### 예시 사용법
            print(colored_text('저장 하지 않습니다.', 'red'))
            print(colored_text('저장 합니다.', 'green'))
            default,red,green,yellow,blue, magenta, cyan, white, rest
            '''
            colors = {
                'default': '\033[99m',
                'red': '\033[91m',
                'green': '\033[92m',
                'yellow': '\033[93m',
                'blue': '\033[94m',
                'magenta': '\033[95m', #보라색
                'cyan': '\033[96m',
                'white': '\033[97m',
                'bright_black': '\033[90m',  # 밝은 검정색 (회색)
                'bright_red': '\033[91m',  # 밝은 빨간색
                'bright_green': '\033[92m',  # 밝은 초록색
                'bright_yellow': '\033[93m',  # 밝은 노란색
                'bright_blue': '\033[94m',  # 밝은 파란색
                'bright_magenta': '\033[95m',  # 밝은 보라색
                'bright_cyan': '\033[96m',  # 밝은 청록색
                'bright_white': '\033[97m',  # 밝은 흰색
                'reset': '\033[0m'
            }
            color_code = colors.get(color, colors['default'])
            bold_code = '\033[1m' if bold else ''
            reset_code = colors['reset']

            return f"{bold_code}{color_code}{text}{reset_code}"
    def b(str):print( F.colored_text(str,'blue'))
    def y(str):print( F.colored_text(str,'yellow'))
    def r(str):print( F.colored_text(str,'red'))
    def g(str):print( F.colored_text(str,'green'))