링크드 리스트(Linked List) 2

https://zuha.tistory.com/entry/링크드리스트LinkedList1

링크드 리스트(Linked List) 1

이전 포스팅에 이어서 포스팅 시작!

 

3. 링크드 리스트의 장단점 (C언어에서의 배열과 링크드 리스트)

장점

- 데이터 공간을 미리 할당하지 않아도 된다.

( 배열은 미리 데이터 공간을 할당해야 한다. )

 

단점

- 연결을 위한 별도 데이터 공간이 필요하므로 저장공간 효율이 높지 않다.

( 각 데이터마다 다음 노드를 가리킬 주소 포인터를 저장할 공간을 별도로 가지고 있어야 한다. )

 

- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.

( 데이터를 찾을 때

배열은 인덱스 번호가 있어서 뒤에 있는 데이터를 찾을 때도 인덱스 번호로 해당 데이터를 직접적으로 가져올 수 있다.

이에 반해 링크드 리스트는 뒤에 있는 데이터를 찾으려면 맨 앞에 있는 데이터부터 시작해서 주소를 확인하고 다음 노드를 찾는 것을 반복하기 때문에 찾는 시간이 필요하다. )

 

- 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다.

 

 

4.  링크드 리스트의 복잡한 기능 1 (링크드 리스트 데이터 사이에 데이터를 추가)

링크드 리스트는 유지 관리에 부가적인 구현이 필요하다.

 

node = head
while node.next:
    print(node.data)
    node = node.next
print(node.data)

현재 노드에 들어가 있는 데이터를 출력해보면 1 ~ 9 까지 들어가있는 것을 확인할 수 있다.

 

node3 = Node(1.5) # 1과 2 사이에 데이터를 추가해보기

node = head
search = True
while search: # search가 True이면
    if node.data == 1: # 현재 node.data가 1이 될 때까지 다음 노드를 찾아간다.
      search = False
    else:
      node = node.next

node_next = node.next
node.next = node3
node3.next = node_next

node = head
while node.next:
    print(node.data)
    node = node.next
print(node.data)

출력해보면 1과 2 사이에 1.5 노드가 추가된 것을 확인할 수 있다.

 

 

5. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

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


class NodeMgmt:
    def __init__(self,data):
        self.head = Node(data)
    
    def add(self,add):
        if self.head == '': 
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
    
    def desc(self): # 순회하는 코드
        node = self.head
        while node:
            print(node.data)

Node class에는 2개의 데이터를 가지는 객체를 만들 수 있는 형태로 구성하면 된다.

NodeMgmt class는 객체를 만들 때 맨 앞에 있는 노드가 가지는 데이터 값까지 같이 받아서 맨 앞에 있는 노드를 생성하고

맨 앞에 있는 노드의 데이터 주소 값을 head 값으로 저장을 하는 형태로 구성한다.

linkedlist1 = NodeMgmt(0)
linkedlist1.desc()

NodeMgmt 클래스를 만들면서 데이터를 동시에 넣어줘서 0이라는 데이터를 가진 노드가 객체로 만들어진다.

NodeMgmt 객체의 속성 값으로 저장이 된다. 그리고 그 객체가 linkedlist1이라는 변수에 저장된다.

객체의 desc 함수를 호출하면 함수 안에 있는 head 값, 지금 생성된 0을 가지고 있는 노드의 주소부터 시작해서 순회하면서 노드에 있는 데이터 값을 출력을 한다.

지금은 데이터가 1개 만들어졌기 때문에 0 하나가 출력된다.

for data in range(1, 10):
    linkedlist1.add(data)
linkedlist1.desc()

바로 위에 있는 코드로 인해 0이 가장 먼저 출력되고 for문을 실행하면 1 ~ 9까지의 노드가 생성된다.

데이터 연결 리스트를 맨 앞에서부터 찾아가면서 데이터를 출력하는 형태가 된다.