[Algorithm][01] 자료구조 Part: 배열, 큐, 스택, 링크드리스트

[ 자료구조 Part ]

Stack

Stack은 프로세스 함수 동작 방식에서 많이 쓰인다.

Process Stack이 Stack이라는 Data Structure을 기반으로 만들어짐.

=> 위 내용을 자신 있게 말 할 수 있어야 한다.

 

선입후출 Stack

 

❤️ 장점 ❤️

구현이 쉽고 구조가 단순

 

Process 실행 = 빠른 속도를 요구하는 작업이므로

함수의 동작을 이 Stack이라는 Data Structure를 이용하는 것이다.

 

단점;;;

Data 최대 개수를 미리 정해야 한다.

따라서 데이터 저장 공간의 낭비가 발생할 수 있다.

 

my_list[-1]

마지막 Index의 값을 가져온다.

 

del my_list[-1]

del Keyword는 List, Dictionary에 사용이 가능?

 

---

 

Linked List (링크드 리스트, 연결 리스트)

※ Programming Quiz, 가벼운 Interview 등에서 Linked List를 가볍게 구현하는 문제가 나오곤 하므로 꼭 알고 있어야 한다.

 

해당 자료구조는 Node로 구성이 되어 있다.

Node = Data의 값을 저장하는 공간 + Pointer(Data가 저장되어 있는 공간을 가리키는 주소의 값)를 가지는 공간

Pointer : 각 Node 안에서 다음이나 이전 노드와의 연결 정보를 가지고 있다.

 

 

< 배열과의 차이점 >

배열은 미리 크기를 지정해야 하므로 예약된 공간 이상의 데이터는 저장할 수 없다.

하지만 Linked List는 미리 크기를 지정할 필요가 없다.

 

 

   >> Python으로 구현하기

Linked List를 구현하기 위해서는 객체지향 문법을 숙지하고 있어야 한다. 만약 제대로 알고 있지 못하다면 기재된 사이트의 11~12번을 학습하고 다시 들을 것.

 

class Node:
	def __init__(self, data, next = None):
    	self.data = data
        self.next = next
        
def add(data):
	node = head
    while node.next:	# True라면, 다음 Node를 가리키는 주소가 있다, 즉 다음 Node가 있따는 뜻
    	node = node.next
    # False라면, node.next = None이라면 마지막 Node라는 뜻
    node.netx = Node(data)
    
node1 = Node(1)
head = node1
for index in range(1, 10):
	add(index)

 

단점

 

- 다음 Data의 주소 Pointer를 저장할 공간도 지니고 있어야 하기 때문에 저장공간 효율이 높지 않다.

- 배열과는 달리 Index 번호가 없고 연결 정보를 찾는 데 시간이 필요하므로 접근 속도가 느리다.

  => Node와 Node 사이에 New Node를 삽입할 때 번거롭고 오래 걸린다.

 

 

 

Double Linkded List (덥르 링크드 리스트, 이중 연결 리스트)

Linked List의 변형된 형태 

이전 Node의 주소도 함께 저장 => 양방향으로 연결되어 Node 탐색이 양쪽으로 모두 가능

 

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

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)  # 생성한 노드를 head에 대입
        self.tail = self.head

    def insert(self, data):
        if self.head == None:   # head가 초기화되어 있는지...
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)    # 마지막 node이면 입력받은 data를 New Node로 만들기
            node.next = new # None으로 설정되어 있는 node.next에 new Node를 연결
            new.prev = node # New Node 의 prev에 현재 node를 연결
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next


double_linked_list = NodeMgmt(0)    # 클래스명()으로 head값을 초기화하거나
for data in range(1, 10):
    double_linked_list.insert(data) # Class 내 insert 함수에서
double_linked_list.desc()

 

 

연습3: 위 코드에서 노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수를 만들고 테스트하기

19:02

함수명: search_from_head

 

 

연습4: 위 코드에서 노드 데이터가 특정 숫자인 노드 에 데이터를 추가하는 함수를 만들고 테스트하기