개요

링크드 리스트는 기본적으로 노드로 구성되어있고 그 노드가 연결될 형태로 구성되어있다.
일종의 체인같은 구조로 구성되어있다고 보면 된다.

가장 Singly Linked List를 기준으로 노드에는 data부분과 next부분이 있다

이번에는 Singly Linked List를 기준으로 설명할 것이다.

설명

위 이미지는 Singly Linked List로 LinkedList라고 하면 가장 쉽게 떠오르는 형태의 이미지이다.

각 노드에는 data부분과 next부분이 있다

그리고 리스트의 진입지점을 가리키는 head가 존재한다.

Data는 일반적으로 저장하고 싶은 데이터가 들어가고 Next에는 다음 노드를 가리키는 포인터가 들어간다.

Singly Linked List를 이용하면 마지막 노드의 next는 null이 된다.

Linked List에는 여러가지 형태가 있는데 종류는 다음과 같다.

Circuler Linked List: 끝 노드의 next부분이 맨앞 노드를 가리키게 하는 형태

• 이 경우 첫노드의 구별은 head라는 노드 관리 포인터를 따로 만들어서 관리한다.

Doubly Linked List: 각 노드의 previus와 next를 동시에 가지는 형태

• 여기서 Circuler형식이 합쳐진 Doubly Circuler Linked List도 있다.

구성요소

Data : 실제 저장할 값
Next : 다음 노드에 대한 포인터
isEmpty : LinkedList가 비어있는지에 대한 정보를 확인하는 메소드

장단점

✅ 장점:

• 중간에 노드를 삽입하거나 삭제할 때 속도가 빠름(O(1)).
• 크기가 동적으로 변할 수 있으며, 미리 크기를 정할 필요 없음.
• 메모리가 분산되어 사용 가능.

❌ 단점:

• 특정 인덱스의 데이터에 접근하기 위해 순차적으로 접근해야 하므로 접근 속도가 느림(O(n)).
• 포인터를 저장하기 위한 추가 메모리 공간이 필요함.

in Swift

import Foundation

class Node<T: Equatable>{
    let value: T?
    var next: Node?
    
    init(_ value: T) {
        self.value = value
    }
    init(){
        self.value = nil
        self.next = nil
    }
}


class SingleLinkedList<T: Equatable> {
    private var head: Node<T>?
    
    func append(_ value: T) {
        let node = Node(value)
        if let head = head {
            head.next = node
        } else {
            self.head = node
        }
    }
    func insert(value: T, at: Int){
        var tmpNode = Node<T>(value)
        
        if let head = head {
            if at == 0 {
                tmpNode.next = head
                self.head = tmpNode
            }else{
                
            }
        }else{
            self.head = tmpNode
        }
        
    }
    func removeFirst(){
        print("\(head?.value) removed")
        head = head?.next
    }
    func removeLast(){
        var cursor: Node<T>? = head
        
        while cursor?.next != nil {
            if cursor?.next?.next == nil {
                print("\(cursor?.next?.value) removed")
                cursor?.next = nil
                break
            }
            cursor = cursor?.next
        }
    }
    func remove(at: Int){}
    
    //void타입으로 하고 결과를 print하는걸로
    func find(value: T){
        var cursor: Node<T>? = head
        
        while cursor?.next != nil {
            if cursor?.next?.value == value{
                if let next = cursor?.next { print(next.value) }
            }
            cursor = cursor?.next
        }
        
        print("data not found")
        
    }
    
    func get(at: Int) -> T?{
        var cursor: Node<T>? = head
        var cnt: Int = 0
        
        
        if at >= size() {
            return nil
        }
        else{
            while cnt > at {
                if cnt == at {
                    return cursor!.value
                }
                cnt += 1
                cursor = cursor?.next
            }
            
        }
        return nil
    }
    func isEmpty() -> Bool{
        if let head = head {
            return false
        }else{
            return true
        }
    }
    func size() -> Int{
        var cursor: Node<T>? = head
        var count: Int = 0
        while cursor?.next != nil {
            count += 1
            cursor = cursor?.next
        }
        return count
    }
    func printList(){
        var cursor: Node<T>? = head
        
        while cursor?.next != nil {
            print(cursor?.value)
            cursor = cursor?.next
        }
        
        
    }
    
}

정리

Singly Linked List를 기준으로 노드에는 data부분과 next부분이 있다
노드의 마지막과 처음이 연결된 Ciruler Linked List가 있고,
next와 previus값을 가지는 Doubly Linked List,
이와 동시에 Ciruler 형태를 띄는 Ciruler Doubly Linked List 도 있다.

+  그리고 대부분의 데이터구조를 linked list를 이용해서 구현하는것이 가능하다