[자료구조/알고리즘] 링크드 리스트 자료구조 - ItisFuture

출처 : 나

링크드 리스트는

노드와 노드를 이어 제한 없이 생성 가능하다는 장점이 있다.

단점은? 즉각적인 인덱싱의 어려움, 메모리를 많이 먹는다.

 

링크드 리스트의 시작

마지막 노드에 다음 노드를 추가해주는 것을 기억하면 쉽다. ( 기차 놀이 )

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

활용

활용은 어떻게 하기에 따라 다르겠다.

노드 중간에 삽입하기, 노드 삭제하기,,, prev를 설정하여 더블 링크드 리스트 만들기 등

많은 활용이 가능할 것이다. 파이썬의 리스트와 비슷하여 파이썬의 멋짐을 느끼며 내가 작성했던 코드로 마무리 하겟다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
class LinkedList:
    def __init__(self, data):
        self.head = Node(data)
        self.len = 0

    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
        self.len += 1
    
    def insert(self, data,idx):
        node = self.head
        idx_cnt = 0
        self.len += 1
        if idx == 0:
            new_node = Node(data)
            new_node.next = node
            self.head = new_node
            return
        while idx_cnt < idx-1 and node.next:
            node = node.next
            idx_cnt += 1
        new_node = Node(data)
        new_node.next = node.next
        node.next = new_node
    
    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
            
    def find_specify_idx_from_back(self, idx):
        fa_node,sl_node = self.head,self.head
        
        if self.len < idx:
            print('리스트의 길이보다 큰 숫자입력됨')
            return 
        
        for i in range(idx):
            fa_node = fa_node.next
        
        while fa_node:
            fa_node,sl_node = fa_node.next, sl_node.next
        return sl_node.data
        
    def delete_node(self, idx):
        cnt = 0
        node = self.head
        if idx == 0:
            self.head = node.next
            return
        while cnt < idx - 1:
            node = node.next
            cnt += 1
        del_node = node.next
        node.next = node.next.next
        del(del_node)