연결 리스트(Linked List)

• 배열: 파이썬의 리스트. 접근 쉬움, 삽입 어려움. (파이썬의 리스트)
• 연결리스트: 직접 구현. 접근 어려움, 삽입 쉬움.

	배열	연결 리스트
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가/제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간(Overhead)	-	O(N)

연결 리스트(Linked List)는 컴퓨터과학에서 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나이다.

동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며, 연결 구조를 통해 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽다.

연결리스트의 종류

1. 단일 연결 리스트

각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트

2. 이중 연결 리스트

각 원소가 자신의 이전 원소와 다음 원소의 주소를 둘 다 들 고 있는 연결 리스트

3. 원형 연결 리스트

처음과 끝이 연결된 연결 리스트
단일과 이중 둘 다 가능하다

연결리스트의 구현

CASE1. 단일 연결리스트 구현

class ListNode:
    # val: 내가 가진 값, next: 내가 가리키는 것
    def __init__(self, val, next):
        # 나의 value는 val이고,
        self.val = val
        # 나의 next는 next이다.
        self.next = next

# 연결 리스트 생성

class LinkedList:
    # 삽입(, 삭제도 있긴하지만 삽입 기능만을 다루겠다)
    # init이 없어도 생성이 가능하고 pass를 이용할 수도 있다
    def __init__(self):
        # 아무런 자료도 안들고 왔을때,
        self.head = None  # ListNode(None, None) 도 가능하다

    def append(self, val):
        # 아직 입력받은 요소가 없을때
        if not self.head:
            # 다음 요소는 없고 입력받은 값이 head이다
            self.head = ListNode(val, None)
            return

        node = self.head
        while node.next:
            node = node.next
        node.next = ListNode(val, None)

# LinkedList화 시켜보기
lst = [1, 2, 3]
# l1이라는 linkedlist를 만들어준다.
l1 = LinkedList()
for e in lst:
    l1.append(e)
print(l1)

CASE2. 연결리스트 구현 심화

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


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

    def append(self, item):
        if self.head is None:
            self.head = Node(item, None)
            return

        node = self.head
        while node.next:
            node = node.next
        node.next = Node(item, None)

    def get_node(self, index):
        if self.head is None:
            print("List is empty!")
            return None

        curr = 0
        node = self.head
        try:
            if index == 0:
                return node
            while curr < index:
                curr += 1
                node = node.next
            return node
        except:
            print("List is shorter than the index!")
            return

    def add_node(self, index, item):
        new_node = Node(item, None)

        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        try:
            node = self.get_node(index - 1)
            if node.next is None:
                node.next = new_node
                return
            next_node = node.next
            node.next = new_node
            next_node.next = next_node
        except:
            print("List is shorter than the index!")
            return

    def delete_node(self, index):
        if self.head is None:
            print("List is empty!")
            return
        elif index == 0:
            self.head = self.head.next
            return

        try:
            node = self.get_node(index-1)
            node.next = node.next.next
        except:
            print("List is shorter than the index!")
            return

# Test
lst = LinkedList()

lst.append(3)
lst.add_node(1, 5)

• 참고
  연결리스트 블로그 포스팅