[자료구조] - Linked List

Linked List(Head만 존재할 때)

자바로 구현한 linked list

public class LinkedList {


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

    public void append(int value){

        Node newNode = new Node(value);
        if (head == null){
            this.head = newNode;
        } else {
            Node currentNode = this.head;

            while (currentNode.next != null){
                currentNode = currentNode.next;
            }
            currentNode.next= newNode;
        }

    }

    public int get(int index){
        Node current = this.head;

        for (int i = 0; i < index; i++){
            current = current.next;
        }
        return current.getValue();
    }

    public void insertAt(int idx, int value){

        Node current = this.head;

        for (int i = 0 ; i < idx; i++){
            current = current.next;
        }
        Node newNode = new Node(value);
        newNode.next = current.next;
        current.next = newNode;
    }

    public int removeAt(int idx){

        Node before = this.head;

        for (int i =0; i < idx-1; i++){
            before = before.next;
        }
        Node removeNode = before.next;
        before.next = removeNode.next;

        int removeValue = removeNode.getValue();

        removeNode = null;

        return removeValue;

    }

    private class Node {
        int value;
        Node next;

        public Node() {
            this.value = 0;
            this.next = null;
        }

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

        public int getValue() {
            return value;
        }
    }
}

• head만 사용해서 해당 linked list를 구현한다면 append(), remove() - 맨 뒤 삽입, 삭제 작업이 시간 복잡도가 O(n)이 될 것
• tail을 추가해준다면 이 작업 역시 O(1)의 시간복잡도를 가진 메소드가 된다.

 

python으로 구현한 linked list

class Node:
    def __init__(self, value = 0 , next = None):
        self.value = value
        self.next = None


first = Node(1)
second = Node(2)
third = Node(3)

first.next = second
second.next = third
first.value = 6


class LinkedList(Object):
    def __init__(self):
        self.head = None
        
    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while(current.next):
                current = current.next
            current.next = new_node
            pass
        
    def get(self, idx):
        current = self.head
        for _ in range(idx):
            current = current.next
        return current.value

    def insert_at(self, idx, value):
        current = self.head
        for _ in range(idx):
            current = current.next
        new_node = Node(value)

        new_node.next = current.next
        current.next = new_node

    def remove_at(self, idx):
        before = self.head
        for _ in range(idx-1):
            before = current.next
        current = before.next

        before.next = current.next

• 타입을 정의하지 않아서 파이썬만 진행하면 이보다 편할 수 없지만 자바를 같이하고 있어서 헷갈림 

---

Linked List(Head, Tail 존재할 때)

자바로 구현한 linked list

package com.example.data_structure.linkedList;

public class LinkedList {


    Node head;
    Node tail;

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

    public void append(int value){

        Node newNode = new Node(value);
        if (head == null){
            // 처음 데이터를 삽입한다면 head와 tail을 동일한 노드를 가리킬 수 있게 한다.
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = this.tail.next;
        }

    }

    public int get(int index){
        Node current = this.head;

        for (int i = 0; i < index; i++){
            current = current.next;
        }
        return current.getValue();
    }

    public void insertAt(int idx, int value){

        Node current = this.head;

        for (int i = 0 ; i < idx; i++){
            current = current.next;
        }
        Node newNode = new Node(value);
        newNode.next = current.next;
        current.next = newNode;
    }

    public int removeAt(int idx){

        Node before = this.head;

        for (int i =0; i < idx-1; i++){
            before = before.next;
        }
        Node removeNode = before.next;
        before.next = removeNode.next;

        int removeValue = removeNode.getValue();

        removeNode = null;

        return removeValue;

    }

    private class Node {
        int value;
        Node next;

        public Node() {
            this.value = 0;
            this.next = null;
        }

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

        public int getValue() {
            return value;
        }
    }
}

python으로 구현한 linked list

class Node:
    def __init__(self, value = 0 , next = None):
        self.value = value
        self.next = None

class LinkedList(Object):
    def __init__(self):
        self.head = None
        self.tail = None
        
    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            # 포인터와 
            self.tail.next = new_node
            self.tail = self.tail.next
        
    def get(self, idx):
        current = self.head
        for _ in range(idx):
            current = current.next
        return current.value

    def insert_at(self, idx, value):
        current = self.head
        for _ in range(idx):
            current = current.next
        new_node = Node(value)

        new_node.next = current.next
        current.next = new_node

    def remove_at(self, idx):
        before = self.head
        for _ in range(idx-1):
            before = current.next
        current = before.next

        before.next = current.next