연결 리스트

1. 배열, 스택, 큐와 다르게 순차적 리스트가 아님.

2. 순차적 리스트와 다르게 메모리가 연속된 주소일 필요가 없음.

3. 배열에 비해 삽입/삭제가 용이

   ex) 배열의 경우, 원하는 인덱스에 데이터를 삽입하고 싶을 때, 뒤 인덱스의 데이터를 모두 한칸씩 밀고 삽입해야 하기 때문에 O(N), but 연결리스트에서는 앞, 뒤 노드를 알고 있다는 가정 하에 링크를 수정하기만 하면 되기 때문에 O(1)

한 방향 연결리스트의 기본구조

key(데이터), link(다음 노드의 주소)로 이루어진 Node의 연결로 이루어져 있다.

마지막 노드의 링크는 NULL

class Node: 			# 노드를 구성하는 클래스
    def __init__(self,key=None):
        self.key = key
        self.next = None
    def __str__(self):
        return str(self.key)


class SinglyLinkedList:     # 연결리스트 인스턴스를 구성하는 클래스
    def __init__(self):
        self.head = None
        self.size = 0

    def __len__(self):
        return self.size

    def pushFront(self,key): ## 앞 노드부터 뒤에서 밀어넣기
        newNode = Node(key)
        newNode.next = self.head
        self.head = newNode
        self.size += 1

    def pushBack(self,key): ## 뒷 노드부터 앞에서 밀어넣기
        newNode = Node(key)
        if len(self) == 0:
            self.head = newNode
        else:
            tail = self.head
            while tail.next != None:
                tail = tail.next
            tail.next = newNode
        self.size += 1
        
    def popFront(self): ## 앞 노드 삭제연산
        if len(self) == 0:
            return None
        else: ## 하나 이상의 노드가 존재한다면
            x = self.head
            key = x.key
            self.head = x.next
            self.size -= 1
            del x ## 삭제할 노드의 메모리를 완전히 초기화
            return key

    def popBack(self): ## 뒷 노드 삭제연산
        if len(self) == 0:
            return None
        else: ## 하나 이상의 노드가 존재한다면
            prev, tail = None, self.head ## running technique : tail 과 바로 직전 노드 prev를 각각 움직임
            while tail.next != None:
                prev = tail
                tail = tail.next
            if len(self) == 1:
                self.head = None
            else:
                prev.next = None # prev.next = tail.next 도 가능
            key = tail.key
            del tail
            self.size -= 1
            return key
    
    def search(self,key): ## key 값의 노드를 리턴, 없으면 None 리턴
        v = self.head
        while v != None:
            if v.key == key:
                return v
            v = v.next
        return None

    def __iterator__(self): ## iterable이 아니지만 for ~ in 문법을 사용하고 싶을 때
        v = self.head
        while v != None:
            yield v         ## yield가 있는 함수를 generator라고 함, for ~ in ~ 문장을 사용 가능하게 함
            v = v.next

수행시간

pushFront/popFront : 헤드에서 연산을 바로 연산을 수행할 수 있어 O(1)

pushBack/popBack : while문의 반복이 n번 이루어지므로 O(N)

search : 첫 노드부터 끝 노드까지를 모두 확인하므로 O(N)