[LeetCode] 707. Design Linked List

https://leetcode.com/problems/design-linked-list/description/

 

Algorithm

• edge case 제거를 위해 prev <-> next 초기화

---

Python

class ListNode:
    def __init__(self,val):
        self.prev = None
        self.val = val
        self.next = None

class MyLinkedList:

    def __init__(self): # left <-> right
        self.left = ListNode(0)
        self.right = ListNode(0)
        self.left.next = self.right
        self.right.prev = self.left

    def get(self, index: int) -> int:
        cur = self.left.next
        while cur and index > 0:
            cur = cur.next
            index -= 1
        
        # 만약 cur이 None,edge case X 이고 해당 index 찾으면
        if cur and cur != self.right and index == 0:
            return cur.val
        return -1

    def addAtHead(self, val: int) -> None:
        # 새 노드 기준 prev,next
        node, prev, next = ListNode(val), self.left, self.left.next
        node.next, node.prev = next, prev # 새 노드 next,prev 설정
        next.prev = node # 기존 노드와 연결
        prev.next = node

    def addAtTail(self, val: int) -> None:
        # 새 노드 기준 prev,next
        node, prev, next = ListNode(val), self.right.prev, self.right
        node.next, node.prev = next,prev # 새 노드 next, prev 설정
        next.prev = node # 기존 노드와 연결
        prev.next = node

    def addAtIndex(self, index: int, val: int) -> None:
        cur = self.left.next
        while cur and index > 0:
            cur = cur.next
            index -= 1

        if cur and index == 0:
            node, prev = ListNode(val), cur.prev
            node.next, node.prev = cur, prev # 새 노드 next,prev 설정
            cur.prev = node # 기존 노드와 연결
            prev.next = node

    def deleteAtIndex(self, index: int) -> None:
        node = self.left.next

        while node and index > 0:
            node = node.next
            index-=1
        # 만약 cur이 None,edge case X 이고 해당 index 찾으면
        if node and node!=self.right and index ==0:
            node.prev.next = node.next
            node.next.prev = node.prev


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

Java

class ListNode {
    int val;
    ListNode prev;
    ListNode next;
    public ListNode(int val) {
        this.prev = null;
        this.val = val;
        this.next = null;
    }
}

class MyLinkedList {

    ListNode left;
    ListNode right;

    public MyLinkedList() {
        left = new ListNode(0);
        right = new ListNode(0);
        left.next = right;
        right.prev = left;
    }
    
    public int get(int index) {
        ListNode cur = left.next;
        while(cur!=null && index > 0){
            cur = cur.next;
            index-=1;
        }
        if(cur!=null && cur!=right && index == 0){
            return cur.val;
        }
        return -1;
    }
    
    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        ListNode next = left.next;
        ListNode prev = left;
        node.next = next;
        node.prev = prev;
        prev.next = node;
        next.prev = node;
    }
    
    public void addAtTail(int val) {
        ListNode node = new ListNode(val);
        ListNode next = right;
        ListNode prev = right.prev;
        node.next = next;
        node.prev = prev;
        prev.next = node;
        next.prev = node;
    }
    
    public void addAtIndex(int index, int val) {
        ListNode cur = left.next;
        while(cur!=null && index>0){
            cur = cur.next;
            index-=1;
        }
        if(cur!=null && index==0){
            ListNode node = new ListNode(val);
            ListNode next = cur;
            ListNode prev = cur.prev;
            node.next = next;
            node.prev = prev;
            prev.next = node;
            next.prev = node;
        }
    }
    
    public void deleteAtIndex(int index) {
        ListNode cur = left.next;
        while(cur!=null && index>0){
            cur = cur.next;
            index-=1;
        }
        if(cur!=null && cur != right && index==0){
            ListNode next = cur.next;
            ListNode prev = cur.prev;
            prev.next = next;
            next.prev = prev;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */