연결 리스트, Linked List는 노드(Node)와 그 노드를 이어주는 링크(Link)를 이용하여 구현한 자료구조이다.
각 노드들은 데이터(data) 링크로 구성되며 링크는 다음번 노드를 가리키는 포인터이다.
노드를 여러개 이어 붙이면 비엔나 소시지와 비슷한 형태로 그려진다.

연결 리스트는 그 연결 구조에 따라, 단일 연결 리스트, 이중 연결 리스트, 순환 연결 리스트(환형 연결 리스트), 청크 리스트로 나눌 수 있다.

여기서는 가장 기본적인 단일 연결 리스트에 대해서만 다루도록 한다.

1.단일 연결 리스트(Singly Linked List)

1.1 자료형 정의

Node와 그 Node간의 연결을 이어주는 LinkedList 클래스에 대한 정의를 먼저 하고, 그에 대한 연산을 다뤄보자.

• Node 클래스

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

• LinkedList 클래스

  class LinkedList:
      def __init__(self):
          self.nodeCount = 0
          self.head = None
          self.tail = None

  LinkedList 클래스에는 노드의 갯수를 저장하는 변수인 nodeCount와, 첫번째 노드를 가리키는 head, 그리고 마지막 노드를 가리키는 tail 변수로 정의를 하자.

1.2 연산의 정의

연결 리스트에서 사용하는 연산은 6개로 나눌수 있다.

1. 특정원소 참조
2. 리스트 순회
3. 길이 얻어내기
4. 원소 삽입
5. 원소 삭제
6. 두 리스트 합치기

다른 연산들은 구현이 쉬운 반면, 원소 삽입, 원소 삭제 이 두가지의 경우 구현이 까다롭다.

1.2.1 특정원소 참조

def getAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        return None

    i = 1
    curr = self.head
    while i < pos:
        curr = curr.next
        i += 1

    return curr

1.2.2 리스트 순회

def traverse(self):
    result = []
    curr = self.head
    while curr is not None:
        result.append(curr.data)
        curr = curr.next
    return result

1.2.3 길이 얻어내기

def getLength(self):
    return self.nodeCount

1.2.4 원소 삽입

def insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodeCount + 1:
        return False

    if pos == 1:
        newNode.next = self.head
        self.head = newNode

    else:
        if pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        newNode.next = prev.next
        prev.next = newNode

    if pos == self.nodeCount + 1:
        self.tail = newNode

    self.nodeCount += 1
    return True

1.2.5 원소 삭제

def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        raise IndexError

    prev = self.getAt(pos - 1)
    curr = self.getAt(pos)

    if self.nodeCount == 1:
        self.head = None
        self.tail = None
    else:
        if pos == 1:
            self.head = curr.next
        elif pos == self.nodeCount:
            self.tail = prev
            prev.next = None
        else:
            prev.next = curr.next

    self.nodeCount -= 1
    return curr.data

1.2.6 두 리스트 합치기

def concat(self, L):
    self.tail.next = L.head
    if L.tail:
        self.tail = L.tail
    self.nodeCount += L.nodeCount

2.Dummy node를 추가한 단일 연결 리스트

Dummy node를 추가하면 원소의 삽입과 삭제를 더 깔끔하게 구현할 수 있다.

2.1 자료형 정의

• Node 클래스 (동일)

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

• LinkedList 클래스

  class LinkedList:
      def __init__(self):
          self.nodeCount = 0
          self.head = Node(None)
          self.tail = None
          self.head.next = self.tail

2.2 연산의 정의

2.2.1 특정원소 참조

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None

    i = 0
    curr = self.head
    while i < pos:
        curr = curr.next
        i += 1

    return curr

2.2.2 리스트 순회

def traverse(self):
    result = []
    curr = self.head
    while curr.next:
        curr = curr.next
        result.append(curr.data)
    return result

2.2.3 길이 얻어내기

def getLength(self):
    return self.nodeCount

2.2.4 원소 삽입

def insertAfter(self, prev, newNode):
    newNode.next = prev.next
    if prev.next is None:
        self.tail = newNode
    prev.next = newNode
    self.nodeCount += 1
    return True

def insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodeCount + 1:
        return False

    if pos != 1 and pos == self.nodeCount + 1:
        prev = self.tail
    else:
        prev = self.getAt(pos - 1)
    return self.insertAfter(prev, newNode)

2.2.5 원소 삭제

def popAfter(self, prev):
    if prev.next is None:
        return None

    curr = prev.next

    if curr.next is None:
        self.tail = prev

    prev.next = curr.next
    self.nodeCount -= 1
    return curr.data

def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        raise IndexError

    prev = self.getAt(pos - 1)
    return self.popAfter(prev)

2.2.6 두 리스트 합치기

def concat(self, L):
    self.tail.next = L.head.next
    if L.tail:
        self.tail = L.tail
    self.nodeCount += L.nodeCount