링크드리스트 노드의 구현

이전에 만든 노드 클래스는 취약하다. 

 

헤더가 링크드 리스트의 대표이면서

 

첫번째 값이기도 하다. 

 

이 첫번째 값이 삭제될 경우 문제가 발생하게 된다.

 

class LinkedList{

    Node header = null;

    static class Node{
        int data;
        Node next = null;
    }

    public LinkedList() {
        this.header = new Node();
    }

    void append(int d){
        Node end = new Node();
        end.data = d;
        Node n = this.header;
        while(n.next != null){
            n = n.next;
        }
        n.next = end;
    }

    void delete(int d){
        Node n = this.header;
        while(n.next != null){
            if(n.next.data == d){
                n.next = n.next.next;
            }else{
                n = n.next;
            }
        }
    }

    void retrieve(){
        Node n = header.next;
        while(n.next != null){
            System.out.print(n.data + " -> ");
            n = n.next;
        }
        System.out.println(n.data);
    }
}

public class LinkedListNode {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.append(1);
        linkedList.append(2);
        linkedList.append(3);
        linkedList.append(4);
        linkedList.append(5);
        linkedList.retrieve();
        linkedList.delete(1);
        linkedList.retrieve();
    }
}

헤더 부분을 데이터로 사용하지 않기 때문에 첫번째 데이터 

예시의 1번 부분을 삭제 가능하다.

 

파이썬으로 구현

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


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

    # get
    def get(self, idx):
        current = self.head
        for _ in range(idx):
            current = current.next
        return current.value

    # append
    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

    # insert_at
    def insert_at(self, idx, value):
        new_node = Node(value)
        new_node.value = value
        current = self.head

        if idx == 0:
            self.head = new_node
            self.head.next = current
        else:
            for _ in range(idx - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node

    # remove
    def remove(self, idx):
        current = self.head

        if idx == 0:
            self.head = current.next

        for _ in range(idx - 1):
            current = current.next
        current.next = current.next.next

    # get_all
    def print_all(self):
        current = self.head
        while current.next:
            print(str(current.value) + "->", end=' ')
            current = current.next
        print(current.value)


li = LinkedList()
print("노드에 삽입: tail을 활용한 o(1)")
li.append(1)
li.append(2)
li.append(3)
li.append(4)

li.print_all()

print("특정 인덱스에 삽입: o(n)")
li.insert_at(0, 10) # 10 -> 1 -> 2 -> 3 -> 4
li.insert_at(4, 10) # 10 -> 1 -> 2 -> 3 -> 10 -> 4
li.print_all()

print("특정 인덱스 삭제: o(n)")
li.remove(0)
li.print_all() # 1 -> 2 -> 3 -> 10 -> 4

print(li.get(0)) # 1
print(li.get(1)) # 2
print(li.get(2)) # 3
print(li.get(3)) # 10
print(li.get(4)) # 4

 

https://www.youtube.com/watch?v=IrXYr7T8u_s