串列結構

背景知識

OO, 基礎語法

理解問題

設計包含雜湊的串列結構，包含前中後插入，刪除，尋訪，反轉

思路視覺化

node(XYZ) <- node(ABC) <- None

Java

TC:
Add First: O(1), Last: O(n)
Insert: After: O(1)
Delete: O(n)

SC:
Add First: O(1), Last: O(n)
Insert: After: O(1)
Delete: O(1)

import java.security.MessageDigest;

class LinkedList {
    static class Node {
        String data;
        Node next;
    
        Node(String d){
            data = d;
            next = null;
        }
    }
    
    static Node head = null;
    byte[] hash = null;
    
    public static void addFirst(String data){
        // make node
        Node newNode = new Node(data);
        // attach before head
        newNode.next = head;
        head = newNode;
        System.out.print(newNode.data+"\n");
        
        // hash
        try {
            MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
            messageDigest.update(newNode.data.getBytes("UTF-8"));
            String stringHash = new String(messageDigest.digest());
            System.out.print("The hash is:"+stringHash+"\n");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
    public static void addLast(String data){
        // make node
        Node newNode = new Node(data);
        newNode.next = null;
 
 		  // go to last, attach new node
        if (head == null) {
            head = newNode;
        }else {
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
        }
        System.out.print(newNode.data+"\n");

        try {
            MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
            messageDigest.update(newNode.data.getBytes("UTF-8"));
            String stringHash = new String(messageDigest.digest());
            System.out.print("The hash is:"+stringHash+"\n");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static void insertAfter(Node prevNode, String data){
        // build prevNode > newNode > newNode.next
        Node newNode = new Node(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
        System.out.print(newNode.data+"\n");

        try {
            MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
            messageDigest.update(newNode.data.getBytes("UTF-8"));
            String stringHash = new String(messageDigest.digest());
            System.out.print("The hash is:"+stringHash+"\n");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
    public static void deleteNode(String key){
        Node currNode = head, prev = null;
 
        if (currNode != null && currNode.data.equals(key)) {
            head = currNode.next;
            System.out.println(key + " found and deleted");
        }

        while (currNode != null && !currNode.data.equals(key)) {
            prev = currNode;
            currNode = currNode.next;
        }
 
        if (currNode != null) {
            prev.next = currNode.next;
            System.out.println(key + " found and deleted \n");
        }
        if (currNode == null) {
            System.out.println(key + " not found");
        }
    }
    
    // 141. Linked List Cycle  Floyd Algorithm return True/False
    // O(N) Time, O(1) Space
    public static Boolean detectCycle(Node head){
        if(head == null || head.next == null) return false;
        
        Node slow = head, fast = head;
      
        while (fast != null && fast.next != null) {
          slow = slow.next;
          fast = fast.next.next;
        
          if (slow == fast) return true;
        }
        return false;
    }
    
    // 142. Linked List Cycle II  Floyd Algorithm return head
    // O(N) Time, O(1) Space    
   public Node detectCycle2(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // distance of slow and fast is half of cycle
            if (slow == fast) break; 
        }
        
        // fast hit end, no cycle
        if (fast == null || fast.next == null) return null; 
        
        // start from head, Synchronize with slow, when head == slow, that is cycle start point
        while (head != slow) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }

    public static void deletePosition(int index){
        Node currNode = head, prev = null;
 
        if (index == 0 && currNode != null) {
            head = currNode.next; // Changed head
            System.out.println(index + " position element deleted");
        }
 
        int counter = 0;
        while (currNode != null) {
            if (counter == index) {
                prev.next = currNode.next;

                System.out.println(index + " position element deleted");
                break;
            } else {
                prev = currNode;
                currNode = currNode.next;
                counter++;
            }
        }
 
        if (currNode == null) {
            System.out.println(index + " position element not found");
        }
    }
    
    public static void reverse(){
        Node cur = head, prev = null, next = null;
        
        while (cur != null) {
            next = cur.next;
            cur.next = prev;
            
            // shift to next node
            prev = cur;
            cur = next;
        }
        
        head = prev;
    }    
    
    public static Node reverseRec(Node head, Node newHead){
        if (head == null) return newHead;
        Node next = head.next;
        head.next = newHead;
        return reverseRec(next, head); // head > next; newHead > head
    }
    
    public static void printList(){
        Node currNode = head;
 
        while (currNode != null) {
            System.out.print(currNode.data + " ");
            currNode = currNode.next;
        }
        System.out.println("\n");
    }
    // overloaded
    public static void printList(Node node) {
        while (node != null) {
            System.out.print(String.valueOf(node.data) + " ");
            node = node.next;
        }
    }
 
    public static void main(String[] args){
        LinkedList list = new LinkedList();
 
        list.addFirst("A");
        list.addFirst("B");
        list.addFirst("C");
        list.insertAfter(list.head.next, "000");
        list.addLast("Z"); 
        
        System.out.println("Given Linked List");
        list.printList();
        
        System.out.println("Loop? "+ list.detectCycle(list.head));
        
        // https://web.ntnu.edu.tw/~algo/Function.html#4
        System.out.println("Loop point? "+ list.detectCycle2(list.head));
        
        System.out.println("Delete node B");        
        list.deleteNode("B");
        list.printList();  

        System.out.println("Delete position 1");          
        list.deletePosition(1);
        list.printList(); 
        
        System.out.println("Reversed Linked List");
        list.reverse();
        list.printList();
        
        System.out.println("Rec Reversed Linked List");
        Node node = reverseRec(list.head, null);
        printList(node);      
    }
}

>
java -cp /tmp/58myPYH7S0 LinkedList
A
The hash is:U????d?y]9	q?????r?O?U????????
B
The hash is:?~p?D??K??J?7???K?p?b??m?2
\
C
The hash is:k#???]??????5]?'}??	9?e[??

000
The hash is:*??tj?T:???????:???o?3?)G"(U?
Z
The hash is:??????iTm??y??P_*!Y????kN???
Given Linked List /n
C B 000 A Z 

Loop? false

Loop point? null

Delete node B
B found and deleted 

C 000 A Z 

Delete position 1
1 position element deleted
C A Z 

Reversed Linked List
Z A C 

Rec Reversed Linked List
C A Z

Python

TC:
Add First: O(1), Last: O(n)
Insert: After: O(1)
Delete: O(n)

SC:
Add First: O(1), Last: O(n)
Insert: After: O(1)
Delete: O(1)

基礎結構

class Node:
    def __init__(self, data):
      self.data = data
      self.next = None
 
class LinkedList:
    # Function to initialize head
    def __init__(self):
      self.head = None
      self.hash = None

新增

def add_first(self, new_data):
  # 1. make node
  if not isinstance(new_data, Node):
    new_node = Node(new_data)
  # 2. node point to list head
  new_node.next = self.head
  # 3. head move to new head
  self.head = new_node
  # 4. hash
  # self.hash = hash(new_node) # same object, same hash result
  
  print(new_node.data)
  hash_ = hash((new_node.data, new_node.next))
  print('The hash is:', end = '')
  print(hash_)
  new_node.hash = hash_
  
def add_last(self, new_data):
  # 1. make node
  if not isinstance(new_data, Node):
    new_node = Node(new_data)
  
  # 2. Linked List is empty, new node as head
  if self.head is None:
    self.head = new_node
    return

  # 3. Traverse till the last node
  last = self.head
  while (last.next):
        last = last.next
  # 4. Change the next of last node
  last.next =  new_node
  
  print(new_node.data)
  hash_ = hash((new_node.data, new_node.next))
  print('The hash is:', end = '')
  print(hash_)
  new_node.hash = hash_

插入

def insert_after(self, prev_node, new_data):
  if prev_node is None:
    print("The given previous node must inLinkedList.")
    return

  # 1. make node
  if not isinstance(new_data, Node):
    new_node = Node(new_data)
  # 2. point to old node pointed to
  new_node.next = prev_node.next
  # 3. prev point to this node
  prev_node.next = new_node
    
  print(new_node.data)
  hash_ = hash((new_node.data, new_node.next))
  print('The hash is:', end = '')
  print(hash_)
  new_node.hash = hash_

刪除

def deleteNode(self, key):
  # 1. store head
  temp = self.head
  
  if temp == None: return
    
  # 2. key is in head
  if temp is not None and temp.data == key:
      self.head = temp.next
      temp = None
      return

  # 3. Search for the key to be deleted,
  while temp is not None:
    if temp.data == key:
      break
    prev = temp
    temp = temp.next

  # 4. Unlink tne node
  prev.next = temp.next
  temp = None

反轉, 遞迴，非遞迴

def reverse(self):
  # Two pointer, current, prev
  cur = self.head
  prev = None

  # prev > cur > next >> prev < cur < next
  while cur is not None:
    next = cur.next # store next node
    cur.next = prev # change next node to previous

    # shift to next node
    prev = cur
    cur = next
    
  self.head = prev # reset head

def reverseRec(self, head):
  # If head is empty or has reached the list end
  if head is None or head.next is None:
      return head

  # Reverse the rest list
  newHead = self.reverseRec(head.next)

  # Put first element at the end
  head.next.next = head
  head.next = None

  # Fix the header pointer
  return newHead

顯示

# Utility function to print the linked LinkedList
def printList(self): # __iter__(self):
  temp = self.head
  
  while(temp):
    print(temp.data, end = " ") # yield node
    temp = temp.next

main

if __name__=='__main__':
  llist = LinkedList()
  llist.add_first("A")
  llist.add_first("B")
  llist.add_first("C")
  llist.insert_after(llist.head.next, "000")
  llist.add_last("Z")

  print()
  print("Given Linked List")
  llist.printList()

  print()
  print("Delete node B")
  llist.deleteNode("B")
  llist.printList()
  
  print("\nReversed Linked List")
  llist.reverse()
  llist.printList()
  
  llist.head = llist.reverseRec(llist.head)
  print("\nRec Reversed Linked List")
  llist.printList()
  
>
A
The hash is:-6923208582321617352
B
The hash is:8939411171582669658
C
The hash is:364725502475584520
000
The hash is:-6125763954762708938
Z
The hash is:647066987114918698

Given Linked List
C B 000 A Z 
Delete node B
C 000 A Z 
Reversed Linked List
Z A 000 C 
Rec Reversed Linked List
C 000 A Z

ref

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)