1. 링크드 리스트(Linked List)

• 본래 C언어에서는 중요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원
• 본래 배열은 사전에 데이터 공간을 할당하고, 데이터를 순차적으로 저장 및 인덱스와 1:1로 가리킬 수 있지만 링크드 리스트는 사전에 데이터 공간을 미리 할당하지 않아도 되고, 데이터가 필요할때마다 새로운 공간에 데이터를 만들고 화살표로 기존 데이터 리스트와 연결하면 됨
• 하지만 이런 기능을 파이썬에서는 리스트 타입이 모든 기능을 지원한다.

1. 노드 기본 구조

- 노드는 데이터를 담을 수 있는 변수와 다음 주소를 가리키는 변수 총 두개가 존재한다.
노드가 하나만 존재한다면 다음을 가리키는 주소값은 NULL을 가리키게 된다.

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

2. 노드 추가

마지막 노드일때 next가 가리키고 있는 값은 NULL이라는 점을 이용해 노드를 추가해주었습니다.

  def add(self, item):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(item)

3. 노드 삭제

def remove(self, item):
        if self.head.val == item:
            self.head = self.head.next
        else:
            cur = self.head
            while cur.next is not None:
                if cur.val == item:
                    self.removeItem(item)
                    return
                cur = cur.next

def removeItem(self, item):
        cur = self.head
        while cur.next is not None:
            if cur.next.val == item:
                nextnode = cur.next.next
                cur.next = nextnode
                break

4. 노드 역순으로 변경

  def reverse(self):
        prev = None
        cur = self.head
        while cur is not None:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        self.head = prev