4장. 단순 연결 리스트 | Ch.4 Simple Linked List

Chapter 04

단순 연결 리스트

Simple Linked List

Part 1  단순 연결 리스트의 개념 · Concept of Simple Linked List
Part 2  단순 연결 리스트의 구현 · Implementation of Simple Linked List
Part 3  단순 연결 리스트의 응용 · Applications of Simple Linked List

01

Part 1

단순 연결 리스트의 개념

Concept of Simple Linked List

약 1시간 · Approx. 1 hour

생활 속 단순 연결 리스트

Linked Lists in Everyday Life

한국어

우리 주변의 연결 리스트

방문할 맛집을 지도 위에 순서대로 연결한 것처럼, 서로 떨어진 곳에 위치한 데이터를 화살표로 연결해 순서를 표현하는 방식이 단순 연결 리스트입니다.

🗺️ 보물찾기 쪽지

첫 번째 쪽지를 찾으면 "다음 힌트는 나무 아래"라고 적혀 있고, 그 쪽지를 찾으면 또 다음 위치를 알려줍니다. 위치는 흩어져 있지만 순서대로 따라갈 수 있습니다.

🚇 지하철 노선도

각 역은 실제로 서로 다른 곳에 떨어져 있지만, "다음 역"이라는 연결 정보를 따라가면 순서대로 이동할 수 있습니다.

🔗 웹 페이지 하이퍼링크

서로 다른 서버에 저장된 웹 페이지들이 링크로 연결되어 있어, 클릭을 따라가면 순서대로 다음 페이지로 이동합니다.

핵심 포인트

데이터가 물리적으로 어디에 있는지는 중요하지 않습니다. 화살표(링크)만 따라가면 항상 정해진 순서대로 데이터를 찾을 수 있습니다.

English

Linked Lists Around Us

Just like connecting restaurants on a map in the order you plan to visit them, a simple linked list connects scattered data with arrows to express order.

🗺️ Treasure Hunt Clues

The first note says "the next hint is under the tree." Finding that note reveals the next location. The spots are scattered, but you can follow them in order.

🚇 Subway Route Map

Each station is physically located in a different place, but following the "next station" connection lets you move through them in order.

🔗 Web Page Hyperlinks

Web pages stored on different servers are connected by links — clicking through them takes you to the next page in sequence.

Key Point

It doesn't matter where the data is physically located. Following the arrows (links) always lets you find data in the correct order.

단순 연결 리스트의 개념

Concept of Simple Linked List

한국어

단순 연결 리스트란?

노드들이 물리적으로 떨어진 곳에 위치합니다.
각 노드가 저장된 메모리 번지(주소)도 순차적이지 않습니다.
노드에 저장된 화살표(링크)를 따라가면 선형 리스트와 동일한 순서로 데이터를 얻을 수 있습니다.

English

What is a Simple Linked List?

Nodes are physically scattered across memory.
The memory address of each node is not sequential.
Following the arrows (links) stored in each node produces the same order as a linear list.

선형 리스트 vs 단순 연결 리스트

Linear List vs Linked List

한국어

삽입/삭제 오버헤드 비교

선형 리스트는 중간에 데이터를 삽입하거나 삭제할 때 많은 데이터를 이동시켜야 하는 오버헤드가 발생합니다. 단순 연결 리스트는 해당 노드의 앞뒤 링크만 수정하면 됩니다.

구분	선형 리스트	단순 연결 리스트
삽입/삭제	많은 데이터 이동 필요	링크만 수정
메모리 사용	데이터만 저장	데이터 + 링크 저장
검색	인덱스로 즉시 접근	처음부터 순차 탐색

English

Comparing Insert/Delete Overhead

In a linear list, inserting or deleting data in the middle requires shifting many elements, creating overhead. In a simple linked list, only the neighboring links need to be modified.

Aspect	Linear List	Linked List
Insert/Delete	Requires shifting data	Only modify links
Memory usage	Data only	Data + link
Search	Instant index access	Sequential traversal

노드 구조

Node Structure

한국어

노드(Node) = 데이터 + 링크

데이터(Data): 실제로 저장하고자 하는 값
링크(Link): 다음 노드를 가리키는 포인터
마지막 노드의 링크는 None으로 설정하여 리스트의 끝을 표시합니다.

English

Node = Data + Link

Data: the actual value being stored
Link: pointer to the next node
The last node's link is set to None to mark the end of the list.

노드 삽입 원리

Node Insertion Principle

한국어

삽입 3단계

1새로운 노드를 생성한다.

2새 노드의 링크가 다음 노드를 가리키게 한다.

3이전 노드의 링크가 새 노드를 가리키게 한다.

English

Three Steps of Insertion

1Create a new node.

2Set the new node's link to point to the next node.

3Set the previous node's link to point to the new node.

노드 삭제 원리

Node Deletion Principle

한국어

삭제 2단계

1이전 노드의 링크를, 삭제할 노드의 링크(다음 노드)로 변경한다.

2삭제할 노드를 메모리에서 제거한다(del).

Fig 4-5. Node Deletion Process

English

Two Steps of Deletion

1Change the previous node's link to the link (next node) of the node being deleted.

2Remove the deleted node from memory (del).

Fig 4-5. Node Deletion Process

Code04-01 · 노드 생성과 연결

Node Creation and Linking

한국어

클래스로 노드를 만들고 직접 연결하기

Node 클래스를 정의하고, 노드 5개를 각각 만들어 link 속성으로 순서대로 연결합니다.

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

node1 = Node()
node1.data = "다현"

node2 = Node()
node2.data = "정연"
node1.link = node2

node3 = Node()
node3.data = "쯔위"
node2.link = node3

node4 = Node()
node4.data = "사나"
node3.link = node4

node5 = Node()
node5.data = "지효"
node4.link = node5

print(node1.data, end = ' ')
print(node1.link.data, end = ' ')
print(node1.link.link.data, end = ' ')
print(node1.link.link.link.data, end = ' ')
print(node1.link.link.link.link.data, end = ' ')

실행 결과다현 정연 쯔위 사나 지효

English

Creating Nodes with a Class and Linking Them Manually

Define the Node class, create 5 nodes, and connect them in order using the link attribute.

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

node1 = Node()
node1.data = "Dahyun"

node2 = Node()
node2.data = "Jungyeon"
node1.link = node2

node3 = Node()
node3.data = "Tzuyu"
node2.link = node3

node4 = Node()
node4.data = "Sana"
node3.link = node4

node5 = Node()
node5.data = "Jihyo"
node4.link = node5

print(node1.data, end = ' ')
print(node1.link.data, end = ' ')
print(node1.link.link.data, end = ' ')
print(node1.link.link.link.data, end = ' ')
print(node1.link.link.link.link.data, end = ' ')

Execution ResultDahyun Jungyeon Tzuyu Sana Jihyo

Code04-02 · 노드 순회

Node Traversal

한국어

while 문으로 링크를 따라가며 순회

current.link가 None이 될 때까지 계속 다음 노드로 이동하며 데이터를 출력합니다. 노드가 몇 개든 동일한 코드로 처리할 수 있습니다.

# Node 클래스 및 노드 생성은 Code04-01과 동일

current = node1
print(current.data, end = ' ')
while current.link != None :
    current = current.link
    print(current.data, end = ' ')

실행 결과다현 정연 쯔위 사나 지효

핵심 포인트

Code04-01은 노드 개수만큼 .link를 반복해서 써야 하지만, while 순회는 노드 개수가 늘어나도 코드를 바꿀 필요가 없습니다.

English

Traversing by Following Links with a while Loop

Keep moving to the next node until current.link becomes None, printing data along the way. The same code works no matter how many nodes exist.

# Node class and node creation are the same as Code04-01

current = node1
print(current.data, end = ' ')
while current.link != None :
    current = current.link
    print(current.data, end = ' ')

Execution ResultDahyun Jungyeon Tzuyu Sana Jihyo

Key Point

Code04-01 requires chaining .link once per node, but the while traversal needs no code changes even as the list grows.

Part 1 연습문제

Part 1 Practice

한국어

연습 1-1

선형 리스트와 단순 연결 리스트의 차이점을 메모리 구조 관점에서 설명하시오.

연습 1-2

노드의 구성 요소(데이터, 링크)가 각각 어떤 역할을 하는지 설명하시오.

연습 1-3

Code04-01.py에서 node3을 삭제하려면 어떤 코드를 추가해야 하는지 작성하시오.

English

Practice 1-1

Explain the difference between a linear list and a simple linked list from a memory structure perspective.

Practice 1-2

Explain the role of each node component (data, link).

Practice 1-3

What code must be added to Code04-01.py to delete node3?

02

Part 2

단순 연결 리스트의 구현

Implementation of Simple Linked List

약 1시간 30분 · Approx. 1.5 hours

간단 구현 · 중간 노드 삽입

Simple Insert in Middle

한국어

Code04-03 — "재남"을 정연 뒤에 삽입

# node1~node5가 이미 연결되어 있는 상태
newNode = Node()
newNode.data = "재남"
newNode.link = node2.link   # 정연의 링크(쯔위)
node2.link = newNode        # 정연의 링크를 재남으로

Fig 4-6. Simple Middle Insertion

실행 결과 (traversal)다현 정연 재남 쯔위 사나 지효

English

Code04-03 — Insert "Jaenam" after Jungyeon

# node1~node5 are already linked
newNode = Node()
newNode.data = "Jaenam"
newNode.link = node2.link   # Jungyeon's link (Tzuyu)
node2.link = newNode        # set Jungyeon's link to newNode

Fig 4-6. Simple Middle Insertion

Execution Result (traversal)Dahyun Jungyeon Jaenam Tzuyu Sana Jihyo

간단 구현 · 중간 노드 삭제

Simple Delete in Middle

한국어

Code04-04 — "쯔위"(node3) 삭제

node2.link = node3.link   # 쯔위의 링크를 정연의 링크로 복사
del(node3)                # 쯔위 삭제

Fig 4-7. Simple Middle Deletion

실행 결과 (traversal)다현 정연 사나 지효

English

Code04-04 — Delete "Tzuyu" (node3)

node2.link = node3.link   # copy Tzuyu's link to Jungyeon's link
del(node3)                # delete Tzuyu

Fig 4-7. Simple Middle Deletion

Execution Result (traversal)Dahyun Jungyeon Sana Jihyo

일반 구현 · 초기 구조

General Implementation — Initial Structure

한국어

포인터 변수 3개

head, current, pre = None, None, None

head: 리스트의 첫 번째 노드를 가리키는 변수
current: 현재 처리 중인 노드를 가리키는 변수
pre: current의 바로 앞 노드를 가리키는 변수

English

Three Pointer Variables

head, current, pre = None, None, None

head: points to the first node of the list
current: points to the node currently being processed
pre: points to the node right before current

일반 구현 · 리스트 생성 (1)

General — List Creation (1)

한국어

첫 번째 노드 생성

node = Node()
node.data = dataArray[0]
head = node   # head가 첫 번째 노드를 가리킴

리스트의 첫 노드를 만들 때는 head가 곧 새 노드가 됩니다. 아직 다음 노드가 없으므로 링크는 자동으로 None입니다.

English

Creating the First Node

node = Node()
node.data = dataArray[0]
head = node   # head now points to the first node

When creating the first node of the list, head becomes the new node itself. Since there's no next node yet, the link is automatically None.

일반 구현 · 리스트 생성 (2)

General — List Creation (2)

한국어

Code04-05 — 두 번째 노드부터

pre = node          # 현재 노드를 pre로 보관
node = Node()       # 새 노드 생성
node.data = data
pre.link = node     # 이전 노드가 새 노드를 가리킴

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

def printNodes(start) :
    current = start
    if current == None :
        return
    print(current.data, end = ' ')
    while current.link != None:
        current = current.link
        print(current.data, end = ' ')
    print()

memory = []
head, current, pre = None, None, None
dataArray = ["다현", "정연", "쯔위", "사나", "지효"]

if __name__ == "__main__" :
    node = Node()
    node.data = dataArray[0]
    head = node
    memory.append(node)

    for data in dataArray[1:] :
        pre = node
        node = Node()
        node.data = data
        pre.link = node
        memory.append(node)

    printNodes(head)

Fig 4-9. Building a Linked List Step by Step

English

Code04-05 — From the Second Node Onward

pre = node          # save current node as pre
node = Node()       # create a new node
node.data = data
pre.link = node     # previous node points to new node

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

def printNodes(start) :
    current = start
    if current == None :
        return
    print(current.data, end = ' ')
    while current.link != None:
        current = current.link
        print(current.data, end = ' ')
    print()

memory = []
head, current, pre = None, None, None
dataArray = ["Dahyun", "Jungyeon", "Tzuyu", "Sana", "Jihyo"]

if __name__ == "__main__" :
    node = Node()
    node.data = dataArray[0]
    head = node
    memory.append(node)

    for data in dataArray[1:] :
        pre = node
        node = Node()
        node.data = data
        pre.link = node
        memory.append(node)

    printNodes(head)

Fig 4-9. Building a Linked List Step by Step

일반 구현 · printNodes 함수

General — printNodes Function

한국어

리스트 전체를 순회하며 출력

def printNodes(start) :
    current = start
    if current == None :   # 빈 리스트
        return
    print(current.data, end = ' ')
    while current.link != None:
        current = current.link
        print(current.data, end = ' ')
    print()

매개변수 start로 시작 노드(보통 head)를 받습니다.
리스트가 비어있으면(current가 None) 바로 return합니다.
첫 노드를 출력한 후, 링크를 따라 끝까지 순회하며 출력합니다.

실행 결과다현 정연 쯔위 사나 지효

English

Traversing and Printing the Whole List

def printNodes(start) :
    current = start
    if current == None :   # empty list
        return
    print(current.data, end = ' ')
    while current.link != None:
        current = current.link
        print(current.data, end = ' ')
    print()

The parameter start receives the starting node (usually head).
If the list is empty (current is None), it returns immediately.
After printing the first node, it follows the links to print the rest.

Execution ResultDahyun Jungyeon Tzuyu Sana Jihyo

노드 삽입 · 첫 번째 노드

Insert — First Node

한국어

맨 앞에 "화사" 삽입

node.link = head   # 새 노드가 기존 첫 노드를 가리킴
head = node        # head가 새 노드를 가리킴

English

Inserting "Hwasa" at the Front

node.link = head   # new node points to old first node
head = node        # head points to the new node

노드 삽입 · 중간 노드

Insert — Middle Node

한국어

"솔라"를 "사나" 앞에 삽입

current/pre를 이동시켜 삽입 위치를 찾은 후 링크를 연결합니다.

node.link = current   # 새 노드가 현재 노드를 가리킴
pre.link = node       # 이전 노드가 새 노드를 가리킴

English

Inserting "Solar" before "Sana"

Move current/pre to find the insertion point, then reconnect the links.

node.link = current   # new node points to current node
pre.link = node       # previous node points to new node

노드 삽입 · 마지막 노드 · Code04-06

Insert — Last Node

한국어

찾는 데이터가 없으면 맨 끝에 추가

findData를 순회하다 끝까지 못 찾으면 current는 마지막 노드가 되고, 여기에 새 노드를 연결합니다: current.link = node

def insertNode(findData, insertData) :
    global memory, head, current, pre

    if head.data == findData :      # 첫 번째 노드 삽입
        node = Node()
        node.data = insertData
        node.link = head
        head = node
        return

    current = head
    while current.link != None :    # 중간 노드 삽입
        pre = current
        current = current.link
        if current.data == findData :
            node = Node()
            node.data = insertData
            node.link = current
            pre.link = node
            return

    node = Node()                   # 마지막 노드 삽입
    node.data = insertData
    current.link = node

사용 예

insertNode("재남", "문별") → 화사 다현 정연 쯔위 솔라 사나 지효 문별

English

Appending When the Target Isn't Found

If findData is never found while traversing, current ends up being the last node, and the new node is attached there: current.link = node

def insertNode(findData, insertData) :
    global memory, head, current, pre

    if head.data == findData :      # insert as first node
        node = Node()
        node.data = insertData
        node.link = head
        head = node
        return

    current = head
    while current.link != None :    # insert in the middle
        pre = current
        current = current.link
        if current.data == findData :
            node = Node()
            node.data = insertData
            node.link = current
            pre.link = node
            return

    node = Node()                   # insert as last node
    node.data = insertData
    current.link = node

Usage Example

insertNode("Jaenam", "Moonbyul") → Hwasa Dahyun Jungyeon Tzuyu Solar Sana Jihyo Moonbyul

노드 삭제 · 첫 번째 노드

Delete — First Node

한국어

head가 가리키는 노드를 삭제

current = head       # 삭제할 노드 임시 보관
head = head.link     # head를 다음 노드로 이동
del(current)          # 이전 첫 노드 삭제

English

Deleting the Node head Points To

current = head       # temporarily hold node to delete
head = head.link     # move head to the next node
del(current)          # delete the former first node

노드 삭제 · 중간/마지막 노드 · Code04-07

Delete — Middle/Last Node

한국어

pre.link = current.link

def deleteNode(deleteData) :
    global memory, head, current, pre

    if head.data == deleteData :         # 첫 번째 노드 삭제
        current = head
        head = head.link
        del(current)
        return

    current = head                       # 첫 번째 외 노드 삭제
    while current.link != None :
        pre = current
        current = current.link
        if current.data == deleteData :
            pre.link = current.link
            del(current)
            return

사용 예: deleteNode("쯔위") → 정연 사나 지효

English

pre.link = current.link

def deleteNode(deleteData) :
    global memory, head, current, pre

    if head.data == deleteData :         # delete first node
        current = head
        head = head.link
        del(current)
        return

    current = head                       # delete any other node
    while current.link != None :
        pre = current
        current = current.link
        if current.data == deleteData :
            pre.link = current.link
            del(current)
            return

Usage: deleteNode("Tzuyu") → Jungyeon Sana Jihyo

노드 검색 · Code04-08 · 연습문제

Node Search & Part 2 Practice

한국어

findNode() 함수

def findNode(findData) :
    global memory, head, current, pre

    current = head
    if current.data == findData :
        return current
    while current.link != None :
        current = current.link
        if current.data == findData :
            return current
    return Node()   # 빈 노드 반환

head부터 순차적으로 탐색하며 데이터를 비교합니다. 찾으면 해당 노드를, 못 찾으면 빈 Node()를 반환합니다.

연습 2-1 ~ 2-3

1. insertNode() 함수에서 첫 번째 / 중간 / 마지막 삽입을 구분하는 조건을 설명하시오.

2. deleteNode()에서 삭제할 데이터가 리스트에 없을 때 어떤 일이 발생하는지 설명하시오.

3. findNode() 함수를 수정하여 찾은 노드의 위치(인덱스)도 함께 반환하도록 하시오.

English

The findNode() Function

def findNode(findData) :
    global memory, head, current, pre

    current = head
    if current.data == findData :
        return current
    while current.link != None :
        current = current.link
        if current.data == findData :
            return current
    return Node()   # return an empty node

Traverses sequentially from head, comparing data. Returns the matching node if found, or an empty Node() otherwise.

Practice 2-1 ~ 2-3

1. Explain the conditions that distinguish first / middle / last insertion in insertNode().

2. What happens in deleteNode() when the data to delete doesn't exist in the list?

3. Modify findNode() to also return the index position of the found node.

03

Part 3

단순 연결 리스트의 응용

Applications of Simple Linked List

약 1시간 · Approx. 1 hour

정렬된 삽입 · 개념

Sorted Insertion — Concept

한국어

이름 순서대로 자동 삽입

데이터를 입력할 때마다 알파벳(가나다) 순서를 비교하여 알맞은 위치에 자동으로 삽입되도록 만듭니다.

입력 순서: 지민 → 정국 → 뷔 → 슈가 → 진
매번 삽입 시 리스트 전체를 순회하며 위치를 찾습니다.

Fig 4-14. Sorted Insertion Process

English

Auto-Insert in Sorted Order

Each time data is entered, compare it alphabetically (or by Korean order) so it's automatically placed at the correct position.

Input order: Jimin → Jungkook → V → Suga → Jin
Each insertion traverses the whole list to find the position.

Fig 4-14. Sorted Insertion Process

정렬된 삽입 · 동작 과정 (1)

Sorted Insertion — Process (1)

한국어

지민 → 정국 → 뷔

1지민: 리스트가 비어있으므로 head = node (첫 노드).

2정국: "정"이 "지"보다 뒤이므로 지민의 앞에 삽입 → head가 정국을 가리키게 됨.

3뷔: "뷔"가 "정"보다 앞이므로 다시 맨 앞에 삽입 → head = 뷔.

매번 head.data[0] > namePhone[0] 조건으로 맨 앞 삽입 여부를 판단합니다.

주의

정렬 기준은 이름의 첫 글자가 아니라 전체 값 비교이지만, 여기서는 리스트의 [0]번 요소(이름)를 비교합니다.

English

Jimin → Jungkook → V

1Jimin: list is empty, so head = node (first node).

2Jungkook: "Jun" sorts before "Jim" alphabetically is false here — it's inserted before Jimin using the Korean order rule → head now points to Jungkook.

3V: "V" sorts before "Jun", so it's inserted at the front again → head = V.

Each time, the condition head.data[0] > namePhone[0] decides whether to insert at the front.

Note

The sort key is not just the first character but the entire value — here we compare element [0] (the name) of each list entry.

정렬된 삽입 · 동작 과정 (2)

Sorted Insertion — Process (2)

한국어

슈가 → 진

4슈가: "슈"는 "뷔"보다 뒤, "정"보다 앞이므로 뷔와 정국 사이(중간)에 삽입.

5진: "진"은 모든 노드보다 뒤이므로 리스트의 끝에 삽입 (while 루프를 끝까지 순회 후 current.link = node).

최종 순서: 뷔 → 슈가 → 정국 → 지민 → 진

핵심 포인트

중간 삽입과 끝 삽입 모두 current, pre를 이동하며 위치를 찾는 동일한 while 루프 구조를 사용합니다.

English

Suga → Jin

4Suga: sorts after "V" but before "Jungkook", so it's inserted between V and Jungkook (middle).

5Jin: sorts after every existing node, so it's appended at the end of the list (the while loop runs to completion, then current.link = node).

Final order: V → Suga → Jungkook → Jimin → Jin

Key Point

Both middle insertion and end insertion use the same while-loop structure that moves current and pre to find the position.

Code04-09 · 전체 코드

Complete Code

한국어

makeSimpleLinkedList() 함수

def makeSimpleLinkedList(namePhone) :
    global memory, head, current, pre
    printNodes(head)

    node = Node()
    node.data = namePhone
    memory.append(node)
    if head == None :
        head = node
        return

    if head.data[0] > namePhone[0] :
        node.link = head
        head = node
        return

    current = head
    while current.link != None :
        pre = current
        current = current.link
        if current.data[0] > namePhone[0]:
            pre.link = node
            node.link = current
            return

    current.link = node

dataArray = [["지민", "010-1111-1111"], ["정국", "010-2222-2222"],
             ["뷔", "010-3333-3333"], ["슈가", "010-4444-4444"],
             ["진", "010-5555-5555"]]

English

makeSimpleLinkedList() Function

def makeSimpleLinkedList(namePhone) :
    global memory, head, current, pre
    printNodes(head)

    node = Node()
    node.data = namePhone
    memory.append(node)
    if head == None :
        head = node
        return

    if head.data[0] > namePhone[0] :
        node.link = head
        head = node
        return

    current = head
    while current.link != None :
        pre = current
        current = current.link
        if current.data[0] > namePhone[0]:
            pre.link = node
            node.link = current
            return

    current.link = node

dataArray = [["Jimin", "010-1111-1111"], ["Jungkook", "010-2222-2222"],
             ["V", "010-3333-3333"], ["Suga", "010-4444-4444"],
             ["Jin", "010-5555-5555"]]

Code04-09 · 실행 결과

Execution Result

한국어

삽입할 때마다 출력되는 중간 상태

함수 맨 앞에서 printNodes(head)를 호출하므로, 삽입 직전의 리스트 상태가 매번 출력됩니다.

                                            # 지민 삽입 전: 리스트 없음
['지민', '010-1111-1111']                    # 정국 삽입 전
['정국', '010-2222-2222'] ['지민', '010-1111-1111']  # 뷔 삽입 전
['뷔', '010-3333-3333'] ['정국', '010-2222-2222'] ['지민', '010-1111-1111']  # 슈가 삽입 전
['뷔', '010-3333-3333'] ['슈가', '010-4444-4444'] ['정국', '010-2222-2222'] ['지민', '010-1111-1111']  # 진 삽입 전

최종 리스트['뷔', '010-3333-3333'] ['슈가', '010-4444-4444']
['정국', '010-2222-2222'] ['지민', '010-1111-1111']
['진', '010-5555-5555']

English

Intermediate State Printed on Every Insert

Because printNodes(head) is called at the top of the function, the list state right before each insertion is printed.

                                            # before inserting Jimin: list empty
['지민', '010-1111-1111']                    # before inserting Jungkook
['정국', '010-2222-2222'] ['지민', '010-1111-1111']  # before inserting V
['뷔', '010-3333-3333'] ['정국', '010-2222-2222'] ['지민', '010-1111-1111']  # before inserting Suga
['뷔', '010-3333-3333'] ['슈가', '010-4444-4444'] ['정국', '010-2222-2222'] ['지민', '010-1111-1111']  # before inserting Jin

Final List['뷔', '010-3333-3333'] ['슈가', '010-4444-4444']
['정국', '010-2222-2222'] ['지민', '010-1111-1111']
['진', '010-5555-5555']

응용예제 1 · 사용자 입력 정보 관리

App Example 1 — User Info Management

한국어

Ex04-01.py — 이메일 순으로 정렬 삽입

사용자가 이름과 이메일을 입력하면, 이메일 주소를 기준으로 정렬된 위치에 자동 삽입합니다.

def makeSimpleLinkedList(nameEmail) :
    global memory, head, current, pre
    node = Node()
    node.data = nameEmail
    memory.append(node)
    if head == None :
        head = node
        return
    if head.data[1] > nameEmail[1] :
        node.link = head
        head = node
        return
    current = head
    while current.link != None :
        pre = current
        current = current.link
        if current.data[1] > nameEmail[1]:
            pre.link = node
            node.link = current
            return
    current.link = node

# 메인: 이름과 이메일을 입력받아 이메일 기준으로 자동 정렬

실행 예이름 : 정연
Email : jy@abc.com
더 입력할까요?(y/n) y
이름 : 다현
Email : dh@zzz.com
더 입력할까요?(y/n) n
['정연', 'jy@abc.com'] ['다현', 'dh@zzz.com']

English

Ex04-01.py — Sorted Insertion by Email

When the user enters a name and email, the entry is automatically inserted at the correct sorted position by email address.

def makeSimpleLinkedList(nameEmail) :
    global memory, head, current, pre
    node = Node()
    node.data = nameEmail
    memory.append(node)
    if head == None :
        head = node
        return
    if head.data[1] > nameEmail[1] :
        node.link = head
        head = node
        return
    current = head
    while current.link != None :
        pre = current
        current = current.link
        if current.data[1] > nameEmail[1]:
            pre.link = node
            node.link = current
            return
    current.link = node

# main: read name/email, auto-sort by email

Example RunName : Jungyeon
Email : jy@abc.com
More? (y/n) y
Name : Dahyun
Email : dh@zzz.com
More? (y/n) n
['Jungyeon', 'jy@abc.com'] ['Dahyun', 'dh@zzz.com']

응용예제 2 · 로또 추첨

App Example 2 — Lotto Drawing

한국어

Ex04-02.py — random 모듈 활용

1~45 사이 숫자 중 중복 없이 6개를 추첨하여 정렬된 연결 리스트로 관리합니다.

import random

def makeLottoList(num) :
    # 정수를 기준으로 정렬 삽입 (로직은 이름 삽입과 동일)
    ...

def findNumber(num) :
    # 이미 뽑힌 번호인지 검사
    ...

lottoCount = 0
while True:
    lotto = random.randint(1,45)
    if findNumber(lotto) :
        continue
    lottoCount += 1
    makeLottoList(lotto)
    if lottoCount >= 6 :
        break
printNodes(head)

실행 예3 7 15 22 31 44

English

Ex04-02.py — Using the random Module

Draw 6 unique numbers between 1 and 45 and manage them in a sorted linked list.

import random

def makeLottoList(num) :
    # sorted insertion by integer (same logic as name insertion)
    ...

def findNumber(num) :
    # check whether the number was already drawn
    ...

lottoCount = 0
while True:
    lotto = random.randint(1,45)
    if findNumber(lotto) :
        continue
    lottoCount += 1
    makeLottoList(lotto)
    if lottoCount >= 6 :
        break
printNodes(head)

Example Run3 7 15 22 31 44

선형 리스트 vs 단순 연결 리스트 요약

Summary Comparison

한국어

정리표

구분	선형 리스트	단순 연결 리스트
저장 방식	연속 메모리	분산 메모리
삽입/삭제	O(n) 이동 필요	O(1) 링크 변경
검색	O(1) 인덱스 접근	O(n) 순차 탐색
메모리	데이터만	데이터 + 링크

English

Summary Table

Aspect	Linear List	Linked List
Storage	Contiguous memory	Scattered memory
Insert/Delete	O(n) shifting required	O(1) link change
Search	O(1) index access	O(n) sequential search
Memory	Data only	Data + link

Part 3 연습문제

Part 3 Practice

한국어

연습 3-1

Code04-09.py에서 이름 대신 전화번호 순으로 정렬하려면 어떻게 수정해야 하는가?

연습 3-2

Ex04-02.py의 로또 프로그램에서 findNumber() 함수가 없으면 어떤 문제가 발생하는가?

연습 3-3

선형 리스트보다 단순 연결 리스트가 유리한 실생활 예를 2가지 이상 제시하시오.

English

Practice 3-1

How would you modify Code04-09.py to sort by phone number instead of name?

Practice 3-2

What problems occur in Ex04-02.py's lotto program without the findNumber() function?

Practice 3-3

Give at least 2 real-world examples where a linked list is more advantageous than a linear list.