[Python] 배열, 연결리스트

#자료구조의 종류
- 배열(Array)
- 연결리스트(Linked List)
- 스택(Stack)
- 큐(Queue)
- 그래프(Graph)
- 트리(Tree)

---

1. 배열(Array) #파이썬에는 없는 개념(list와 그나마 가장 유사함)

- 가장 기본적인 자료구조, 선형 데이터구조

- 배열 생성되는 순간 인덱스 부여(인덱스 표기법)

- 배열 크기 고정

- 배열크기가 고정되어 있어 데이터를 추가, 삭제과정이 비효율적
    ~ 더 큰 배열을 추가로 만들고 이전 값을 복사한 후 새로운 값 추가
    ~ 더 작은 배열을 추가로 만들고 삭제할 값을 빼고 이전 값을 복사

- 데이터가 삭제되면 남은 공간이 생겨 메모리 낭비 발생

- 하나의 변수명으로 여러 데이터를 관리가능함.

---

2. 연결리스트(Linked List)

단방향 연결리스트

2-1. 단방향 연결 리스트

- 선형 데이터구조

- 데이터는 메모리의 임의 공간에 저장

- 데이터의 순서에 따라 노드의 주소를 이용하여 서로 연결시킨 구조(값뿐만 아니라 다음에 올 값의 위치정보도 함께 나열)
    ~ 노드 = 데이터부+주소부

- 새로운 데이터의 추가, 삭제가 용이함.(배열과 다르게 추가, 삭제 시 재구성 필요 없음.)

- 배열과 다르게 추가, 삭제 시 재구성 필요 없음.

- 메모리의 효율적 사용 가능함.

- 노드의 주소가 끊어지면 다음 노드를 찾기가 어려움.

- 조회 속도가 상대적으로 느림.

class Node :

    def __init__(self, data) :
        self.data = data #값
        self.next = None #다음 노드의 위치 정보 - 주소부에 들어가는 것!!

class LinkedList :

    def __init__(self) :
        self.head = None #맨 처음 노드를 가리킴 (값+위치)

    def print(self) :
        tmp = self.head
        while tmp :
            print(tmp.data, end = ", ")
            tmp = tmp.next

    def firstAdd(self, new_data) : #시간복잡도 O(1)
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def lastAdd(self, new_data): #시간복잡도 O(n)
        new_node = Node(new_data) #new_data의 위치정보
        tmp = self.head # 맨 앞 node

        while tmp.next :
            tmp = tmp.next

        tmp.next = new_node

    def middleAdd(self, index, new_data):
        index = index - 1 # 이전 노드
        tmp = self.head

        while index > 0 and tmp !=None :
            tmp = tmp.next
            index = index - 1
            
        #tmp : 추가하려는 노드의 이전 노드
        new_node = Node(new_data)
        new_node.next = tmp.next #새 노드의 위치 정보에 다음 노드 정보(원래 그 위치에 있던 노드의 위치 정보) 삽입
        tmp.next = new_node  # 이전 노드 위치정보에 새 위치 정보 삽입


    def firstDelete(self) :
        tmp = self.head
        self.head = tmp.next       


    def lastDelete(self): 
        tmp = self.head 

        while tmp.next.next :
            tmp = tmp.next

        #tmp : 맨 마지막 노드의 이전 노드
        tmp.next = None


    def middleDelete(self, index):

        if index == 0 :
            tmp = self.head
            self.head = tmp.next               

        else :
            index = index  -1# 이전 노드
            tmp = self.head
            
            while index > 0 and tmp !=None :
                tmp = tmp.next
                index = index - 1

            tmp.next = tmp.next.next # 노드 위치 정보에 다다음 위치 정보 삽입()


    def getData(self, index) :
        
        tmp = self.head
            
        while index > 0 and tmp !=None :
            tmp = tmp.next
            index = index - 1

        return tmp.data


         

ll = LinkedList()

zero = Node(9) #one 변수 : node(9)의 위치 정보
one = Node(13) #two 변수 : node(13)의 위치 정보
two = Node(7)
three = Node(20)

ll.head = zero #시작 숫자 9
zero.next = one # 다음 숫자 13의 위치 정보(9 -> 13)
one.next = two #9 -> 13 -> 7 
two.next = three #9 -> 13 -> 7 ->20

'''
ll.firstAdd(15) #맨 앞에 15 추가
ll.lastAdd(10) # 맨 뒤에 10 추가
ll.middleAdd(2, 5) #2번 위치에 5 추가

'''
##ll.firstDelete() #맨 앞 삭제
##ll.lastDelete() #맨 뒤 삭제
##ll.middleDelete(2)

ll.print()

print(ll.getData(1))

---

양방향 연결 리스트

2-2.양방향 연결 리스트(이중 연결 리스트)

- 3개의 구성요소(앞주소, 뒷주소, 값)

- 이전 노드를 알고 있으므로 맨 끝 노드를 삭제할 때 바로 삭제 가능함.

- 단방향 연결 리스트보다 더 복잡하지만, 효율성이 높음

class Node :

    def __init__(self, data, prev=None, next=None) :
        self.data = data 
        self.prev = prev 
        self.next = next

class DoubleLinkedList :

    def __init__(self) :
        self.head = None #맨 처음 노드를 가리킴 (위치+값+위치)
        self.tail = None #맨 끝 노드를 가리킴(위치+값+위치)

    def print(self) : #화면 출력
        tmp = self.head
        while tmp :
            print(tmp.data, end = ", ")
            tmp = tmp.next

    def firstAdd(self, new_data) :   #시간복잡도 O(1)
        if self.head == None :  #노드가 하나도 없을 때
            new_node = Node(new_data)
            self.head = new_node
            self.tail = new_node

        else :  #노드가 한 개 이상 있을 때
            new_node = Node(new_data)
            tmp = self.head
            tmp.prev = new_node #기존에 맨 앞에 있던 노드의 prev 위치정보에 새 노드의 위치정보 넣기
            new_node.next = tmp #새 노드의 next 위치정보에 기존 노드의 prev 위치정보 넣기
            self.head = new_node

    def lastAdd(self, new_data) : #시간복잡도 O(1)
        if self.head == None :  #노드가 하나도 없을 때
            new_node = Node(new_data)
            self.head = new_node
            self.tail = new_node
            
        else: #노드가 한 개 이상 있을 때
            new_node = Node(new_data)
            tmp = self.tail #tmp: 맨 마지막 노드
            tmp.next = new_node #기존에 맨 뒤에 있던 노드의 next 위치정보에 새 노드의 위치정보 넣기
            new_node.prev = tmp #새 노드의 pre 위치정보에 기존 노드의 위치정보 넣기
            self.tail = new_node

    def middleAdd(self, index, new_data):
        index = index - 1 # 이전 노드
        tmp = self.head

        while index > 0 and tmp !=None :
            tmp = tmp.next
            index = index - 1
            
        #tmp : 추가하려는 노드의 이전 노드
        new_node = Node(new_data)
        new_node.next = tmp.next #새 노드의 next 위치 정보에 다음 노드 정보(원래 그 위치에 있던 노드의 위치 정보) 삽입
        tmp.next.prev = new_node # 다음 노드(원래 그 위치에 있던 노드)의 prev 위치 정보에 새 노드 위치정보 삽입
        tmp.next = new_node  # 이전 노드 위치정보에 새 위치 정보 삽입
        new_node.prev = tmp#새 노드의 prev 위치 정보에 이전 노드 위치정보 삽입

    def firstDelete(self) :
        if self.head.prev == None and self.head.next ==None : #노드가 한 개일 때
            self.head = None
            self.tail = None
            
        else : #노드가 두 개 이상일 때
            tmp = self.head
            self.head = tmp.next
            tmp.next.prev = None

    def lastDelete(self) :
        if self.head.prev == None and self.head.next ==None : #노드가 한 개일 때
            self.head = None
            self.tail = None
            
        else : #노드가 두 개 이상일 때
            tmp = self.tail.prev #이전 노드
            tmp.next = None
            self.tail = tmp
            
    def reverseprint(self) : #역순 출력        
        tmp = self.tail
        while tmp != None :
            print(tmp.data, end = ", ")
            tmp = tmp.prev


dll = DoubleLinkedList()

dll.firstAdd(10)#10
dll.firstAdd(5) #5, 10

dll.lastAdd(7) #5, 10, 7
dll.lastAdd(15) #5, 10, 7, 15

dll.middleAdd(2, 11) #5, 10, 11, 7 , 15

dll.firstDelete() #10, 11, 7, 15
dll.lastDelete() #10, 11, 7

dll.print()
print()
dll.reverseprint() #7, 11, 10