링크드리스트(LinkedList)란?

 

 

 

배열과 차이점 : 배열은 미리 특정 순차적인 연결된 데이터 공간을 확보해놓고 데이터를 쓰고 읽지만 링크드리스트는 미리 예약하지않고, 필요할때마다 데이터를 추가 가능하다.

 

링크드 리스트의 구조: 데이터저장공간 및 다음데이터공간을 가르키는 주소를 가짐(노드)

 

장점

- 미리 데이터 공간을 할당하지 않아도 됨

 

단점

- 연결을 위한 별도의 데이터 공간이 필요, 저장공간 효율 x

- 인덱스로 바로 접근하는 배열과 달리 탐색에 시간이 오래걸림

- 중간 데이터 삭제, 혹은 삽입시 부가 작업 필요

 

간단하게 python으로 구현한 add,delete기능을 첨가한 링크드리스트

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
class NodeMgmt:
    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)
        
    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
    
    def delete(self, data):
        if self.head == '':
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data:
            temp = self.head
            self.head = self.head.next
            del temp
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next