[자료구조] 리스트

리스트(List)

• 데이터 요소들을 순서대로 저장하는 자료구조이다.
• 배열 또는 동적 배열로 구현될 수 있다.
• 인덱스를 사용하여 각 요소에 접근할 수 있다.

# 리스트
from typing import Any

class List:
    def __init__(self,size:int)->None:
        self.size = size
        print(f"{self.size} 크기의 리스트 생성!")
        self.__container = [None] * self.size
    
    def getter(self,index:int)->Any: return self.__container[index]
    
    def setter(self,item:Any,index:int)->None : self.__container[index] = item
    
    def add(self,item:Any,index:int)->None:
        self.__container[index] = item
    
    def remove(self,index:int)->None:
        self.__container[index] = None

    def showAll(self)->None:
        print("---------------List---------------")
        print(self.__container)

l = List(10)
l.showAll()
l.add("hello",2)
l.showAll()

 

연결 리스트(Linked List)

• 데이터 요소들을 노드(Node)라는 개별적인 단위로 저장하는 자료구조 이다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• 메모리 상에서 각 노드가 연속적으로 위치하지 않고, 흩어져 있을 수 있다.
• 데이터의 추가, 삭제가 비교적 쉽고 빠르지만, 임의의 위치에 직접 접근하기 어렵다.

# 연결 리스트
from typing import Any

# 노드
class Node:
    def __init__(self,item:Any,next:Any)->None:
        self.__item = item # 저장할 값
        self.__next = next # 다음 노드
    def getItem(self)->Any: return self.__item
    def getNode(self)->Any: return self.__next
    def setItem(self,item:Any)->None: self.__item = item
    def setNode(self,next:Any)->None: self.__next = next
    def __del__(self) : print("노드 삭제!")

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

    def add(self,item:Any)->None:
        if self.head == None : # 아무것도 없는 상태
            self.head = Node(item,None)
            self.cur = self.head
        else :
            self.cur.setNode(Node(item,None))
            self.cur = self.cur.getNode()

    def __search(self,key:Any)->Node:
        next = self.head
        target = None
        prTarget = None
        while True:
            if next == None:
                break
            elif next.getNode() != None and next.getNode().getItem() == key:
                target = next.getNode()
                prTarget = next
                break
            
            next = next.getNode()
        
        if target != None:
            return target,prTarget
        else:
            return -1,None

    def remove(self,key)->None:
        t,p = self.__search(key)
        if t == -1:
            print("값이 리스트에 없습니다.")
        else :
            p.setNode(t.getNode())
            del t            

    def showAll(self)->None:
        next = self.head
        while True:
            if next.getNode() == None:
                print(next.getItem())
                break
            else:
                print(f"{next.getItem()} -> ", end='')
                next = next.getNode()

l = LinkedList()
l.add(10)
l.add(20)
l.add(30)
l.add(60)
l.add(40)
l.showAll()
l.remove(70)
l.remove(30)
l.showAll()

"""
10 -> 20 -> 30 -> 60 -> 40
값이 리스트에 없습니다.
노드 삭제!
10 -> 20 -> 60 -> 40
"""

 

이중 연결 리스트(Doubly Linked List)

• 연결 리스트의 한 종류로, 각 노드가 다음 노드 뿐만 아니라 이전 노드를 가리키는 포인터를 가진다.
• 양방향 탐색이 가능하다.
• 데이터의 추가, 삭제, 탐색이 상대적으로 유연하게 이루어진다.
• 각 노드마다 이전 노드를 가리키는 포인터가 추가적으로 필요하므로 메모리 사용량이 증가한다.

# 이중 연결 리스트
from typing import Any

class Node:
    def __init__(self,item:Any,next:Any)->None:
        self.__item = item
        self.__pre = None
        self.__next = None
    def getItem(self)->Any : return self.__item
    def setItem(self,item:Any)->None : self.__item = item
    def getPre(self)->Any : return self.__pre
    def setPre(self,pre:Any)->None : self.__pre = pre
    def getNext(self)->Any : return self.__next
    def setNext(self,next:Any)->None : self.__next = next
    def __del__(self) : print("노드 삭제!")

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.cur = None

    def add(self,item:Any)->None:
        if self.head == None : # 아무것도 없는 상태
            self.head = Node(item,None)
            self.cur = self.head
        else :
            self.cur.setNext(Node(item,None))
            self.cur = self.cur.getNext()

    def __search(self,key:Any)->Node:
        next = self.head
        target = None
        prTarget = None
        while True:
            if next == None:
                break
            elif next.getNext() != None and next.getNext().getItem() == key:
                target = next.getNext()
                prTarget = next
                break

            next = next.getNext()

        if target != None:
            return target,prTarget
        else:
            return -1,None

    def remove(self,key)->None:
        t,p = self.__search(key)
        if t == -1:
            print("값이 리스트에 없습니다.")
        else :
            p.setNext(t.getNext())
            del t

    def showAll(self)->None:
        next = self.head
        while True:
            if next.getNext() == None:
                print(next.getItem())
                break
            else:
                print(f"{next.getItem()} <-> ", end='')
                next = next.getNext()

dl = DoublyLinkedList()
dl.add(10)
dl.add(20)
dl.add(30)
dl.add(60)
dl.add(40)
dl.showAll()
dl.remove(70)
dl.remove(30)
dl.showAll()