節點類

package BlockLinkList;import java.util.ArrayList;public class BlockLinkNode {public BlockLinkNode prev;public BlockLinkNode next;public ArrayList<Integer> list;public BlockLinkNode(BlockLinkNode prev,BlockLinkNode next,ArrayList<Integer> list){this.prev=prev;this.next=next;this.list=list;}}

塊狀鏈表

package BlockLinkList; import java.util.*;public class BlockLinkList {public BlockLinkNode blockLinkNode = null;private int total;public BlockLinkList(){//初始化節點// blockLinkNode = new BlockLinkNode(null,null,list);}public boolean IsExist(int num){boolean isExist = false;BlockLinkNode temp = blockLinkNode;while (temp != null){//判斷是否在該區間內if (temp.list.size()-1 > 0 && num >= temp.list.get(0) && num <= temp.list.get(temp.list.size() - 1)){isExist = temp.list.indexOf(num) > 0 ? true : false;return isExist;}temp = temp.next;}return isExist;}public String Get(int num){int blockIndex = 0;int arrIndex = 0;BlockLinkNode temp = blockLinkNode;while (temp != null){//判斷是否在該區間內if (temp.list.size()-1 > 0 && num >= temp.list.get(0) && num <= temp.list.get(temp.list.size()- 1)){arrIndex = temp.list.indexOf(num);return String.format("當前數據在第{0}塊中的{1}個位置", blockIndex, arrIndex);}blockIndex = blockIndex + 1;temp = temp.next;}String str=null;str="";return str;}public BlockLinkNode Add(int num){return Add(blockLinkNode, num);}private BlockLinkNode Add(BlockLinkNode node, int num){if (node == null){return node;}else{/** 第一步：找到指定的節點*/if (node.list.size()== 0){node.list.add(num);total = total + 1;return node;}//下一步：再比較是否應該分裂塊int blockLen = (int)Math.ceil(Math.sqrt(total)) * 2;//如果該節點的數組的最后位置值大于插入值，則此時我們找到了鏈表的插入節點，//或者該節點的next=null，說明是最后一個節點，此時也要判斷是否要裂開if (node.list.get(node.list.size() - 1) > num || node.next == null){node.list.add(num);//最后進行排序下，當然可以用插入排序解決，O(N)搞定Collections.sort(node.list);//如果該數組里面的個數大于2*blockLen，說明已經過大了，此時需要對半分裂if (node.list.size() > blockLen){//先將數據插入到數據庫int mid = node.list.size()/2-1;//分裂處的前段部分ArrayList<Integer> firstList = new ArrayList<Integer>();//分裂后的后段部分ArrayList<Integer> lastList = new ArrayList<Integer>();//可以在插入點處分裂，也可以對半分裂(這里對半分裂)for(int i=0;i<mid;i++){firstList.add(i,node.list.get(i));}for(int i=mid;i<node.list.size()-1;i++){lastList.add(i,node.list.get(i));}//開始分裂節點，需要新開辟一個新節點ArrayList<Integer> tlist = new ArrayList<Integer>();BlockLinkNode nNode = new BlockLinkNode(null,null,tlist);nNode.list = lastList;nNode.next = node.next;nNode.prev = node;//改變當前節點的next和listnode.list = firstList;node.next = nNode;}total = total + 1;return node;}return Add(node.next, num);}}public BlockLinkNode Remove(int num){return Remove(blockLinkNode, num);}private BlockLinkNode Remove(BlockLinkNode node, int num){if (node == null){return node;}else{//第一步： 判斷刪除元素是否在該節點內if (node.list.size()-1> 0 && num >= node.list.get(num) && num <= node.list.get(node.list.size() - 1)){//定義改節點的目的在于防止remove方法假刪除的情況發生int prevcount = node.list.size();node.list.remove(num);total = total - (prevcount - node.list.size());//下一步： 判斷是否需要合并節點int blockLen = (int)Math.ceil(Math.sqrt(total) / 2);//如果當前節點的數組個數小于 blocklen的話，那么此時改節點需要和后一個節點進行合并//如果該節點時尾節點，則放棄合并if (node.list.size()< blockLen){if (node.next != null){node.list.addAll(node.next.list);//如果下一個節點的下一個節點不為null，則將下下個節點的prev賦值if (node.next.next != null)node.next.next.prev = node;node.next = node.next.next;}else{//最后一個節點不需要合并，如果list=0，則直接剔除該節點if (node.list.size()== 0){if (node.prev != null)node.prev.next = null;node = null;}}}return node;}return Remove(node.next, num);}}public int GetCount(){int count = 0;BlockLinkNode temp = blockLinkNode;System.out.println("各節點數據個數為：");while (temp != null){count += temp.list.size();System.out.println(temp.list.size() + ",");temp = temp.next;}System.out.println("總共有:{0} 個元素"+count);return count;}}

總結

以上是生活随笔為你收集整理的java 块状链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。