Linked List

Linked List?

• linked list는 연결리스트(단방향 연결 리스트)라고도 하는데, 데이터를 노드의 형태로 저장하는 것을 말하며, head와 node(혹은 vertex)들로 구성되어있다.
• 각각의 node는 실제 데이터가 저장되는 data field 와 다음 데이터의 주소값이 저장되는 link field 로 구성된다.
• head는 첫번째 node가 무엇인지를 알려주는 변수이다.

• 프로그래밍적으로 node를 표현할 때에 C와 같은 언어에서는 구조체를 이용하고, 객체지향프로그래밍 언어에서는 객체를 이용한다.
• python의 경우 list 기본 자료형에 linked list 기능이 함께 포함되어 있다.

Linked List vs Array List

• Linked List
  • 각각의 데이터들이 흩어져 있으나 서로 연결되어 있음
  • 장점 : 데이터가 늘어도 비어있는 메모리주소를 이용하여 쉽게 확장해갈 수 있다. 즉 linked list의 크기가 확정적이지 않다. 또한 데이터를 추가/삭제할 때 앞과 뒤의 next값만 바꿔주면 되기 때문에 데이터 추가/삭제가 빠르다.
  • 단점 : 데이터 조회 속도가 느리다. 예를 들어 3번째 element를 찾고자 한다면 1번째, 2번째 순서를 거쳐가야만 3번째 element에 도달할 수 있기 때문이다.
• Array List
  • 같은 element들이 메모리상에 연속적으로 붙어있음
  • 장점 : 인덱스를 이용해 조회를 할 때 랜덤엑세스를 할 수 있기때문에 찾고자하는 데이터의 위치를 알고 있다면 데이터 조회 속도가 빠르다.
  • 단점 : 확장성이 좋지 못하다. 연속적으로 붙어있어야하기 때문에 데이터가 늘어난다면 더 큰 공간으로 데이터 전체를 옮겨야한다. 또한 데이터 추가/삭제를 할 때 빈자리가 생기거나 빈자리를 만들기 위해서 그 뒤에 위치하는 element들을 한칸씩 이동시켜줘야하기 때문에 데이터 추가/삭제가 느리다.

(singly)linked list vs doubly linked list

• linked list는 next라는 필드를 이용하여 다음 node로 이동할 수 있지만 doubly linked list는 previous link field와 next link field가 존재하여 이전 node 또한 알 수 있다.
• doubly linked list
  • 양방향 연결 리스트라고도 한다.
  • 장점 : linked list보다 조회속도가 빠르다. 만약 찾고자하는 데이터의 인덱스가 전체 데이터의 크기의 절반보다 큰다면 뒤에서 조회하는 것이 빠르기 때문이다.
  • 단점 : previous link field도 존재하기 때문에 메모리를 더 많이 사용한다. linked list에 비해 조금 더 복잡하다.

구현 - 연결리스트(linked list)

• insert : 데이터 추가
• delete : 데이터 삭제
• search : 데이터 조회
• print : 현재 리스트 출력
• listNum : 리스트의 요소 개수

# Node 클래스 선언
class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None

# linked list 클래스 선언
class LinkedList:
    def __init__(self):
        self.head = None
        self.count = 0
    
    def insert(self, data, current=self.count):
        new_node = Node(data)
        # 리스트에 노드가 하나도 없을 때
        if self.head == None:
            self.head = new_node
        # 리스트 맨 처음에 넣고 싶을 때
        elif current == 0:
            new_node.next = self.head
            self.head = new_node
        # 리스트 중간 혹은 마지막에 넣고 싶을 때
        else:
            temp1 = self.head    # head를 참조하여 첫번째 노드를 찾아 temp1에 저장 
            current -= 1
            while current != 0:  # new_node를 이전 노드의 next로 지정하기 위해 temp1에 이전 노드를 저장하기 위한 반복문
                temp1 = temp1.next
                current -= 1
            temp2 = temp1.next
            temp1.next = new_node
            new_node.next = temp2
        self.count += 1
    
    
    # 중복 data가 없다는 가정 하에 data를 비교하여 삭제
    def delete(self, data):
        # 리스트에 노드가 하나도 없을 때
        if self.count == 0:
            print("linked list empty!!!")
            return False
        # data가 첫 노드의 데이터와 같을 때
        elif data == self.head.data:
            deleted_data = self.head.data
            self.head = self.head.next
            self.count -= 1
            print("deleted data : ", deleted_data)
            return deleted_data
        # 그 외
        else:
            before = self.head # 이전
            current = self.head.next  # 현재
            check = 0
            while check != self.count:
                if data == current.data:
                    deleted_data = current.data
                    after = current.next
                    before.next = after
                    self.count -= 1
                    print("deleted data : ", deleted_data)
                    return deleted_data
                else:
                    before = current
                    current = before.next
            print("no data")

    def search(self, data):


    def print(self):
        current = self.head
        if self.count == 0:
            print("linked list empty!!!")
            return None
        for i in range(self.count):
            print(current.data)
            current = current.next


    def listNum(self):
        return self.count 
    

참고 사이트
생활코딩 : https://opentutorials.org/module/1335/8821
visualgo : https://visualgo.net/ko/list
https://daimhada.tistory.com/72