자료구조의 구현

  • Sun, Jun 9, 2019
  • 읽는 시간 3분

List 형 자료구조

  • 배열: 크기가 변하지 않음, 중간 값이 지워져도 크기가 일정
  • 리스트: 크기가 변함, 중간 값이 지워지면 뒤에 값이 앞으로 이동

Python example

# Python List
sales_results = [12, 45, 67, 43, 56, 98]

for s in sales_results:
    print ( "The sales result = %d" % ( s ) )

print ( " delete:", sales_results[3])
del sales_results[3]

for s in sales_results:
    print ( "The sales result = %d" % ( s ) )

The sales result = 12
The sales result = 45
The sales result = 67
The sales result = 43
The sales result = 56
The sales result = 98
 delete: 43
The sales result = 12
The sales result = 45
The sales result = 67
The sales result = 56
The sales result = 98

코드 설명: List 를 생성하고 삭제, 출력 예시

연결 리스트 자료구조

  • 연결 리스트
  • 더블 연결 리스트
  • 환형 연결 리스트

연결리스트는 데이터 사이의 관계를 이용하기 때문에

  • 데이터의 중간 삽입과 삭제가 용이
  • 데이터를 서치하기는 불편

Python example

# Python Linked List

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = None # 다음 data

# 1. 연결리스트 생성

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node1.next = node2
node2.next = node3
node3.next = node4

# 2. 구성된 리스트에서 데이터 2 를 지우고 나머지를 연결

del_data = 2

pre_node = node1
next_node = pre_node.next

if pre_node.data == del_data:
    node1 = next_node
    del pre_node

while next_node:
    if next_node.data == del_data:
        pre_node.next = next_node.next
        del next_node
        break
    pre_node = next_node
    next_node = next_node.next

# 3. 구성된 리스트에서 데이터 9 를 삽입
new_node = Node(9)
new_node.next = node1
node1 = new_node

# 4. 결과 출력
node = node1
while node:
    print( node.data )
    node = node.next

9
1
3
4

코드 설명: Node class 를 선언하고 이를 이용해

  • 연결 리스트를 생성하고,
  • 데이터를 삭제,
  • 데이터를 삽입,
  • 최종 결과를 출력 한다.

연결리스트를 이용한 스택 구현

Python example

# Link class
class Link:
    def __init__(self, d1=None, d2=None):
        self.data1 = d1
        self.data2 = d2
        self.next_link = None

    def printLink(self):
        print ( "{", self.data1, ", ", self.data2, "}")

# LinkList class
class LinkList:
    def __init__(self):
        self.first_link = None

    def isEmpty(self):
        return self.first_link == None

    def insert(self, d1, d2):
        if self.first_link == None :
            self.first_link = Link( d1, d2 )
        else:
            tmp_next_link = self.first_link
            self.first_link = Link( d1, d2 )
            # first_link 의 next_link 초기화됨
            self.first_link.next_link = tmp_next_link

    def delete(self):
        rlink = self.first_link
        self.first_link = self.first_link.next_link
        return rlink

    def printList(self):
        curLink = self.first_link
        print ( "Link list" )
        while(curLink != None):
            curLink.printLink()
            curLink = curLink.next_link

def test():
    link_list = LinkList()
    link_list.insert( 1, 100 )
    link_list.insert( 2, 200 )
    link_list.insert( 3, 300 )
    link_list.insert( 4, 400 )
    link_list.insert( 5, 500 )

    link_list.printList()

    while( not link_list.isEmpty() ):
        deletedLink = link_list.delete()
        print ( "delete" )
        deletedLink.printLink()

    link_list.printList()

test()

Link list
{ 5 ,  500 }
{ 4 ,  400 }
{ 3 ,  300 }
{ 2 ,  200 }
{ 1 ,  100 }
delete
{ 5 ,  500 }
delete
{ 4 ,  400 }
delete
{ 3 ,  300 }
delete
{ 2 ,  200 }
delete
{ 1 ,  100 }
Link list

코드 설명: Link class 를 선언하고 이를 이용해 스택을 구현

!TODO https://opentutorials.org/module/1335/8821 여기 자료 참고하여 내용 보강하기

자료구조 (data structure)알고리즘 (algorithm)

댓글