Linked List ?

---

Linked List는 Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결을 이용해서 리스트를 구현한 것을 의미합니다.

• python 의 경우 list 기본 자료형에 linked list 기능이 함께 포함되어 있습니다.
• array list에서는 엘리먼트라는 이름을 사용했지만 linked list와 같이 연결된 엘리먼트들은 노드(node, 마디, 교점의 의미) 혹은 버텍스(vertex, 정점, 꼭지점의 의미)라고 부른다.
• 연결되는 방향에 따라 3가지 종류가 있다.
  • Singly linked list (단일 연결 리스트)
  • Doubly linked list(이중 연결 리스트)
  • Circular linked list(환형 연결 리스트)

Linked List의 장단점 (Singly linked list)

---

장점

• 수정이 O(1)에 이루어진다.
• 수정을 할때마다 동적으로 linked list 크기가 결정되어 배열(Array)에 비해 처음부터 큰 공간을 할당필요가 없다.
• 메모리 관리가 용이하다. (이것이 가장 큰 장점이라고 한다)

단점

• Random Access 이라 Array처럼 index를 통해 탐색이 불가능하다.
• 탐색이 O(n)이 걸린다. (처음부터 끝까지 모두 탐색시 즉)

Array와의 관계

Array와 trade off의 관계를 갖는다.
즉, 어떤 특성이 좋아지면 다른 특성이 나뻐지는 상황을 의미
생활코딩 참조

Implementing Linked List(Singly linked list) in Python

Python으로 linked list(단방향 연결) 클래스로 메소드를 구현해보았다.

---

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

class LinkedList:
    def __init__(self, item):
        self.head = Node(item)

    # 추가 메소드
    def add(self, item):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(item)

    # 삭제 메소드
    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
            print("item does not exist in linked list")

    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
    # 출력 메소드
    def printlist(self):
        cur = self.head
        print("HEAD:: ", end='')
        while cur is not None:
            print(cur.val, '->', end=' ')
            cur = cur.next
        if cur is None:
            print('empty')

    # linked list size 출력 메소드
    def size(self):
        cur = self.head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    # 탐색 메소드
    def search(self, data):
        check = self.head
        for i in range(self.size()):
            if check.val == data:
                print(data, "The data is at the {} index.".format(i+1))
                return None
            check = check.next
        print(data, "Data does not exist in linked list")
        return None

linked = LinkedList(2)

linked.add(3)
linked.add(4)
linked.add(5)
linked.printlist()

linked.remove(3)
linked.printlist()

linked.search(5)
print(linked.size())
	
# HEAD:: 2 -> 3 -> 4 -> 5 -> empty
# HEAD:: 2 -> 4 -> 5 -> empty
# 5 The data is at the 3 index.
# 3