[자료구조] 링크드 리스트 Linked List

Linked List

선형적인 데이터 구조

• 노드 1 -> 노드 2 -> 노드 3 -> ...

각 노드 = 자신의 데이터 + 내 앞 노드의 주소

Linked List를 사용하는 이유 (장점 )

• 배열의 제한 사항 때문.
  1. 배열의 크기가 고정 
  2. 새로운 요소를 삽입하는 데 비용이 많이 듬 ( 공간을 만들고, 기존 요소를 전부 이동해야 함)
• 삽입과 삭제가 용이
• 동적 메모리 할당이 가능
• 크기가 가변적

Linked List의 단점

1. 임의의 위치로 액세스 불가 ( 첫 번째 노드부터 순차적으로 접근해야함 ➡️ 이진 검색이 불가능 )
2. 각 노드마다 내 앞의 노드를 가르키는 데이터를 저장할 공간이 필요

코드 

파이썬

#파이썬

class Node:
    def __init__(self, new_data) -> None:
        self.data = new_data
        self.next = None

class LinkedList:
    def __init__(self) -> None:
        self.head = None
        
    def append(self, data) -> None:
        new_node = Node(data)
        if self.head: 
            cur_node = self.head
            while cur_node.next != None:
                cur_node = cur_node.next
            cur_node.next = new_node
        else:
            self.head = new_node
            
    def appendLeft(self, data) -> None:
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert(self, n, data) -> None:
        new_node = Node(data)
        
        cur_node = self.head
        prev_node = None
        while n:
            prev_node = cur_node
            cur_node = cur_node.next
            n -= 1
            
        prev_node.next = new_node
        new_node.next = cur_node
        
    def __str__(self) -> str:
        
        cur_node = self.head
        res = ""
        while cur_node.next != None:
            res += cur_node.data + " ➡️ "
            cur_node = cur_node.next
        res += cur_node.data
        return res
    
lk = LinkedList()
lk.append("node1")
lk.append("node2")
lk.appendLeft("head")
lk.insert(2, "insert 2")
print(lk)

--출력--
head ➡️ node1 ➡️ insert 2 ➡️ node2

자바

//java

public class 자바연습장{
    public static void main(String[] args) {
        LinkedList lk = new LinkedList();

        lk.append(1);
        lk.append(2);
        lk.append(3);
        lk.insert(2, 222);
        lk.appendLeft(0);

        System.out.println(lk);
    }
    
}

class Node{
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    private Node head;

    public LinkedList(){
        this.head = null;
    }

    public void append(int data) { 
        Node newNode = new Node(data);

        if(this.head == null){
            this.head = newNode;
        } else {
            Node curNode = this.head;
            while(curNode.next != null) {
                curNode = curNode.next;
            }
            curNode.next = newNode;
        }
    }

    public void appendLeft(int data){ 
        Node newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    public void insert(int n, int data){
        Node newNode = new Node(data);
        Node prevNode = null;
        Node curNode = this.head;
        while(n > 1){
            prevNode = curNode;
            curNode = curNode.next;
            n -= 1;
        }
        prevNode.next = newNode;
        newNode.next = curNode;
    }
    public String toString(){
        String res = "";
        Node curNode = this.head;
        while (curNode.next != null){
            res += curNode.data + " -> ";
            curNode = curNode.next;
        }
        res += curNode.data;
        return res;
    }
}
-- 출력 -- 
0 -> 1 -> 222 -> 2 -> 3

 

참고 출처

https://gyoogle.dev/blog/computer-science/data-structure/Linked%20List.html