#2 리스트와 연결리스트

 자료구조는 다양하지만 실제 자료구조를 구현하는 기술은 리스트와 연결 리스트 두 가지이다.

이 둘을 이용해 다양한 자료구조가 만들어진다.

 

*리스트형 자료구조

연속적인 저장의 형태를 가진다.

 - 배열 : 크기가 변하지 않는 리스트형 자료구조, 중간의 값을 지워도 빈칸으로 유지한다.

       배열의 장점 : 접근이 빠르다 (인덱스)

       배열의 단점 : 데이터 추가 삭제가 어렵다. 최대 길이를 지정하면 변경이 어렵다.

 - 리스트 : 크기가 변하는 자료구조, 중간의 값을 지우면 뒤의 것이 앞으로 이동한다.

 

JAVA에서는 배열과 Set으로 제공한다. 

 

*연결 리스트형 자료구조

프로그래머가 자체적으로 구현하여 사용한다. 데이터를 포인터로 연결하여 사용한다. 

 - 연결 리스트 : 저장된 각 데이터가 데이터 + 다음 데이터의 포인터로 이루어졌으며, 한 방향으로만 탐색 가능한 구조

 - 더블 연결 리스트 : 저장된 각 데이터가 이전 데이터의 포인터 + 데이터 + 다음 데이터의 포인터로 이루어졌으며,

                            양 방향 탐색이 가능한 구조

 - 환형 연결 리스트 : 더블 연결 리스트의 양 끝이 연결되어 있는 구조

 

연결 리스트 / 출처 : wikipedia

 

 장점은 삽입과 삭제를 할 때는 전체 데이터의 변동은 없고, 앞 뒤의 연관된 데이터만 변동하면 되고 데이터를 중간에 삽입/삭제하는 과정을 빠르게 수행할 수 있다.

 단점은 특정 데이터를 찾는 것은 포인터를 따라 이동해야 하므로 성능이 떨어진다. 

즉, 데이터의 변화가 많은 상황이라면 연결 리스트를 사용하는 것이 좋다.

 

파이썬으로 구현한 연결 리스트

class Node : #노드 클래스 생성
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
        
def init(): #연결 리스트 생성
    global node1
    
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    
def print_list(): #연결 리스트 출력
    global node1
    node = node1
    
    while node:
        print(node.data)
        node = node.next
    print()

def delete(del_data): #연결 리스트 데이터 삭제 후 나머지 연결
    global node1
    pre_node = node1
    next_node = pre_node.next
    
    if pre_node.data == del_data : #노드1 삭제 시
        node1 = next_node
        del pre_node
        return
    
    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

def insert(ins_data): #연결 리스트 데이터 추가
    global node1
    new_node = Node(ins_data)
    new_node.next = node1
    node1 = new_node

def LinkedList():
    init();
    delete(3)
    insert('9')
    print_list()

LinkedList() #연결 리스트 실행

 

 

gitHub : https://github.com/DevCheonYuJung/data_structure/blob/master/Python_dataStructure/linkedList.py