Java中实现双向链表

一、目标

        最近项目中实现双向链表，同时转为满二叉树。

二、代码

        用java实现双向链表的代码如下：

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class FullBinaryTree {public TreeNode createTree(int[] nums, int i) {if (i >= nums.length || nums[i] == -1) {return null;}TreeNode root = new TreeNode(nums[i]);root.left = createTree(nums, 2 * i + 1);root.right = createTree(nums, 2 * i + 2);return root;}public static int binarySearch(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}
}class ListNode {int val;ListNode prev;ListNode next;ListNode(int x) { val = x; }
}public class DoublyLinkedList {public ListNode createList(int[] nums) {ListNode dummy = new ListNode(-1);ListNode prev = dummy;for (int num : nums) {ListNode node = new ListNode(num);prev.next = node;node.prev = prev;prev = node;}return dummy.next;}public int find(ListNode head, int target) {ListNode curr = head;while (curr != null) {if (curr.val == target) {return curr.val;}curr = curr.next;}return -1;}public ListNode insert(ListNode head, int pos, int val) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode curr = dummy;while (pos > 0) {curr = curr.next;pos--;}ListNode node = new ListNode(val);node.prev = curr;node.next = curr.next;if (curr.next != null) {curr.next.prev = node;}curr.next = node;return dummy.next;}public ListNode modify(ListNode head, int pos, int val) {ListNode curr = head;while (pos > 0) {curr = curr.next;pos--;}curr.val = val;return head;}public ListNode delete(ListNode head, int pos) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode curr = dummy;while (pos > 0) {curr = curr.next;pos--;}ListNode node = curr.next;if (node.next != null) {node.next.prev = curr;}curr.next = node.next;return dummy.next;}public TreeNode toFullBinaryTree(ListNode head) {if (head == null) {return null;}List<Integer> nums = new ArrayList<>();ListNode curr = head;while (curr != null) {nums.add(curr.val);curr = curr.next;}int[] arr = nums.stream().mapToInt(Integer::intValue).toArray();FullBinaryTree fbTree = new FullBinaryTree();return fbTree.createTree(arr, 0);}
}

在以上代码中，ListNode类表示双向链表中的节点，包含一个值和前后两个节点。DoublyLinkedList类中定义了六个方法，分别为：

• createList方法用于根据给定的整数数组创建一个双向链表；
• find方法用于在双向链表中查找目标元素，并返回其值；
• insert方法用于在双向链表中插入新节点；
• modify方法用于修改双向链表中的节点值；
• delete方法用于删除双向链表中的节点；
• toFullBinaryTree方法用于将双向链表转换为一棵满二叉树，并返回根节点。

具体实现见代码。