[DataStructure]Linked List

Linked List

Linked List(연결리스트)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다.

• 노드(node)  : 데이터를 담고 있는 그릇, 주로 class로 구현됩니다.
• 링크(link) : 리스트의 순서를 유지할 수 있게 해주는 연결고리

기본적으로 마지막 노드의 link는 null(None)값을 가지고 있습니다.

Linked List의 장점

Linked 리스트의 가장큰 장점은 삽입과 삭제가 배열보다 효율적이라는 것입니다.

(기본적으로 순열적 구조이기에 배열과만 비교합니다.)

Linked list는 요소 삭제,삽입시 링크값만 바꾸기 때문에 배열에 비해 유리합니다.

Linked List Class로 구현

class Node:   # 각노드를 1개의 클래스로 표현
    def __init__(self, value):
        self.value = value
        self.next  = None 

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

    def set_next(self, next):
        self.tail.next = next
        self.tail      = next

    def print_list(self):
        def _recurse_list(node):
            if node is not None:
                return f" -> {node.value}" + _recurse_list(node.next)

            return ""
         
        return print(f"{self.head.value}{_recurse_list(self.head.next)}")

# Create LinkedList and set its head
linked_list = LinkedList(Node("Mon"))

# Link first Node to second node
linked_list.set_next(Node("Tue"))

# Link second Node to third node
linked_list.set_next(Node("Wed"))

In [1]: linked_list.print_list()
Mon -> Tue -> Wed

Doubly Linked List

Doubly Linked List는 다음 노드 뿐만이 아니라 전 노드의 링크도 가지고 있는 lined list 입니다.

즉, 앞과 뒤 둘다 이동이 가능한 리스트 입니다.

Circular Linked list

Circular Linked List의 꼬리(tail)부분이 머리(head) 부분과 연결 되어 있는 연결 리스트입니다.

Array와 차이점

Array와 마찬가지로 순차열적으로 요소들을 저장한다는 점은 비슷하지만 메모리측면에서 많은 차이를 가지고있습니다.

 

1. Array는 물리적으로 데이터가 메모리상에 순차적으로 존재하지만 Linked List는 각 노드들이 분산되어있고 link로 연결 되어있는점에서 극명하게 차이가 갈립니다.
2. Array는 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 때문에 데이터 접근속도가 매우빠릅니다(indexing)
   - but, Linked List는 링크로 연결하는 방식이기에 index가 존재하지 않아 노드와 링크를 타고넘어가며 접근하기에 접근속도가 떨어집니다.
3. Array는 삽입/삭제시 물리적 shift가 일어나지만 Linked list는 논리적주소(link)를 바꿔주면 되기때문에 훨씬 간편합니다.
4. 동일한 양의 데이터를 저장해도 일반적으로 연결리스트가 배열보다 더 많은 메모리를 차지하게 됩니다
   - Array는 단순 데이터 저장인데 비해 Linked List는 각노드마다 객체를 생성하기 때문입니다.

그렇다면 Linked List는 언제 사용해야 할까!?

전제 : 순서대로 데이터를 입력해야할때!

• 데이터 양이 많지 않고 데이터 삽입/삭제가 빈번하게 이루어질때
• size 증가폭이 클때! (resizing을 염두해둬야한다.)

어디에서 Linked List를 사용하고 있을까?!

 

공부해야할 키워드

더미헤더 노드