数据结构-高层数据结构：集合（Set）【元素不重复】【基于二分搜索树（有序集合O(logn)）、基于平衡二叉树（有序集合O(logn)）、基于链表（无序集合O(n)）、基于哈希表（无序集合O(n)）】

本文主要是介绍数据结构-高层数据结构：集合（Set）【元素不重复】【基于二分搜索树（有序集合O(logn)）、基于平衡二叉树（有序集合O(logn)）、基于链表（无序集合O(n)）、基于哈希表（无序集合O(n)）】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Set.java

package set;/*** 集合** @author ronglexie* @version 2018/8/18*/
public interface Set<E> {/*** 向集合中添加元素** @param e* @return void* @author ronglexie* @version 2018/8/18*/void add(E e);/*** 删除集合中的某个元素** @param e* @return void* @author ronglexie* @version 2018/8/18*/void remove(E e);/*** 查看是否包含某个元素** @param e* @return boolean* @author ronglexie* @version 2018/8/18*/boolean contains(E e);/*** 获取集合的大小** @param* @return int* @author ronglexie* @version 2018/8/18*/int getSize();/*** 判断集合是否为空** @param* @return boolean* @author ronglexie* @version 2018/8/18*/boolean isEmpty();
}

一、基于二分搜索树实现的Set

BinarySearchTree.java

package set;import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;/*** 二分搜索树** @author ronglexie* @version 2018/8/18*/
public class BinarySearchTree<E extends Comparable<E>> {private Node root;private int size;public BinarySearchTree() {root = null;size = 0;}public BinarySearchTree(Node e){root = e;size ++;}public int size(){return size;}public boolean isEmpty(){return size == 0;}/*** 向二分搜索树中添加元素** @param e* @return void* @author ronglexie* @version 2018/8/18*/public void add(E e){root = add(root,e);}/*** 向node为根元素的二分搜索树中插入元素* 递归算法** @param node* @param e* @return void* @author ronglexie* @version 2018/8/18*/@Deprecatedprivate void addDeprecated(Node node,E e){/** 递归终止条件：判断根节点、根a节点的左右节点是否为空*/if(e.equals(node.e)){return;}else if(e.compareTo(node.e) < 0 && node.left == null){node.left = new Node(e);size ++;return;}else if(e.compareTo(node.e) > 0 && node.right == null){node.right = new Node(e);size ++;return;}if(e.compareTo(node.e) < 0){addDeprecated(node.left,e);}else if(e.compareTo(node.e) > 0){addDeprecated(node.right,e);}}/*** 向node为根元素的二分搜索树中插入元素* 递归算法** @param node* @param e* @return void* @author ronglexie* @version 2018/8/18*/private Node add(Node node, E e){//递归终止条件，返回结果为nullif(node == null){size ++;return new Node(e);}if(e.compareTo(node.e) < 0){node.left = add(node.left,e);}else if(e.compareTo(node.e) > 0){node.right = add(node.right,e);}return node;}/*** 判断二分搜索树是否包含某个元素** @param e* @return boolean* @author ronglexie* @version 2018/8/18*/public boolean contains(E e){return contains(root,e);}/*** 判断以node为根元素的二分搜索树是否包含某个元素** @param node* @param e* @return boolean* @author ronglexie* @version 2018/8/18*/private boolean contains(Node node,E e){if(node == null){return false;}if(e.compareTo(node.e) == 0){return true;}else if(e.compareTo(node.e) < 0){return contains(node.left,e);}else /*if(e.compareTo(node.e) < 0)*/{return contains(node.right,e);}}/*** 前序遍历二分搜索树** @param* @return void* @author ronglexie* @version 2018/8/18*/public void preOrder(){preOrder(root);}/*** 前序遍历以node为根节点的二分搜索树* 深度优先遍历，递归实现** @param node* @return void* @author ronglexie* @version 2018/8/18*/private void preOrder(Node node){if(node == null){return;}System.out.println(node.e);preOrder(node.left);preOrder(node.right);}/*** 前序遍历二分搜索树* 深度优先遍历，非递归实现，利用栈结构** @param* @return void* @author ronglexie* @version 2018/8/18*/public void preOrderNR(){Stack<Node> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){Node cur = stack.pop();System.out.println(cur.e);if(cur.right != null){stack.push(cur.right);}if(cur.left != null){stack.push(cur.left);}}}/*** 中序遍历二分搜索树** @param* @return void* @author ronglexie* @version 2018/8/18*/public void inOrder(){inOrder(root);}/*** 中序遍历以node为根节点的二分搜索树* 深度优先遍历，递归实现** @param node* @return void* @author ronglexie* @version 2018/8/18*/private void inOrder(Node node){if(node == null){return;}inOrder(node.left);System.out.println(node.e);inOrder(node.right);}/*** 后序遍历二分搜索树** @param* @return void* @author ronglexie* @version 2018/8/18*/public void postOrder(){postOrder(root);}/*** 后序遍历以node为根节点的二分搜索树* 深度优先遍历，递归实现** @param node* @return void* @author ronglexie* @version 2018/8/18*/private void postOrder(Node node){if(node == null){return;}postOrder(node.left);postOrder(node.right);System.out.println(node.e);}/*** 层序遍历二分搜索树* 广度优先遍历，利用队列结构** @param* @return void* @author ronglexie* @version 2018/8/18*/public void levelOrder(){Queue<Node> nodeQueue = new LinkedList<>();nodeQueue.add(root);while (!nodeQueue.isEmpty()){Node cur = nodeQueue.poll();System.out.println(cur.e);if(cur.left != null){nodeQueue.add(cur.left);}if(cur.right != null){nodeQueue.add(cur.right);}}}/*** 查找二分搜索树的最小值** @param* @return E* @author ronglexie* @version 2018/8/18*/public E minimum(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return minimum(root).e;}/*** 查找以node为根节点二分搜索树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node minimum(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.left == null){return node;}return minimum(node.left);}/*** 查找二分搜索树的最大值** @param* @return E* @author ronglexie* @version 2018/8/18*/public E maximize(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return maximize(root).e;}/*** 查找以node为根节点二分搜索树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node maximize(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.right == null){return node;}return minimum(node.right);}/*** 删除二分搜索树的最大值** @param* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/public E removeMax(){E maximize = maximize();removeMax(root);return maximize;}/*** 删除以node为根的二分搜索树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node removeMax(Node node){if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}node.right = removeMin(node.right);return node;}/*** 删除二分搜索树的最小值** @param* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/public E removeMin(){E minimum = minimum();removeMin(root);return minimum;}/*** 删除以node为根的二分搜索树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}/*** 删除二分搜索树中的指定元素** @param e* @author ronglexie* @version 2018/8/18*/public void remove(E e){root = remove(root,e);}/*** 删除以node为根的二分搜索树中的指定元素* 深度优先遍历，递归实现** @param node* @param e* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node remove(Node node, E e) {if(node == null){return null;}if(e.compareTo(node.e) < 0){node.left = remove(node.left,e);return node;}else if(e.compareTo(node.e) > 0){node.right = remove(node.right,e);return node;}else /*if(e.compareTo(node.e) == 0)*/{// 删除右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}// 删除左子树为空的情况else if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}// 删除左子树、右子树均不为空的情况else {// 1、删除后用后继节点替代该位置(后继节点即待删除节点右子树中的最小节点)// 获得后继节点Node successor = minimum(node.right);// 删除后继节点，并让待删除节点的右子树成为后继节点的右子树successor.right = removeMin(node);// 让待删除节点的左子树成为后继节点的左子树successor.left = node.left;// 将待删除节点的左、右子节点置为空node.left = node.right = null;return successor;/**// 2、删除后用前驱节点替代该位置(前驱节点即待删除节点左子树中的最大节点)// 获得前驱节点Node predecessor = maximize(node.left);// 删除前驱节点，并让待删除节点的左子树成为前驱节点的左子树predecessor.left = removeMax(node);// 让待删除节点的右子树成为前驱节点的右子树predecessor.right = node.right;// 将待删除节点的左、右子节点置为空node.left = node.right = null;return predecessor;*/}}}@Overridepublic String toString() {StringBuilder result = new StringBuilder();generateBSTString(root,0,result);return result.toString();}/*** 生成二分搜索树的字符** @param node* @param depth* @param result* @return void* @author ronglexie* @version 2018/8/18*/private void generateBSTString(Node node, int depth, StringBuilder result) {if (node == null) {result.append(generateBSTString(depth)+"null\n");return;}result.append(generateBSTString(depth)+node.e+"\n");generateBSTString(node.left,depth+1,result);generateBSTString(node.right,depth+1,result);}/*** 生成表示深度的字符** @param depth* @return java.lang.String* @author ronglexie* @version 2018/8/18*/private String generateBSTString(int depth) {StringBuilder result = new StringBuilder();for (int i = 0; i < depth; i++) {result.append("--");}return result.toString();}/*** 节点类** @author ronglexie* @version 2018/8/18*/private class Node{public E e;public Node left,right;public Node(E e){this.e = e;left = null;right = null;}}
}

BinarySearchTreeSet.java

package set;/*** 利用二分搜索树实现集合* 不包含重复元素** @author ronglexie* @version 2018/8/18*/
public class BinarySearchTreeSet<E extends Comparable<E>> implements Set<E> {private BinarySearchTree<E> binarySearchTree;public BinarySearchTreeSet() {binarySearchTree = new BinarySearchTree<>();}@Overridepublic void add(E e) {binarySearchTree.add(e);}@Overridepublic void remove(E e) {binarySearchTree.remove(e);}@Overridepublic boolean contains(E e) {return binarySearchTree.contains(e);}@Overridepublic int getSize() {return binarySearchTree.size();}@Overridepublic boolean isEmpty() {return binarySearchTree.isEmpty();}
}

二、基于平衡二叉树(AVL)实现的Set

AVLTree.java

package set;import java.util.ArrayList;/*** AVL平衡二叉树** @author ronglexie* @version 2018/9/1*/
public class AVLTree<K extends Comparable<K>,V> {private Node root;private int size;public AVLTree() {root = null;size = 0;}/*** 获取某个节点的高度** @param node* @return int* @author ronglexie* @version 2018/9/1*/private int getHeight(Node node){if(node == null){return 0;}return node.height;}/*** 获取某个节点的平衡因子** @param node* @return int* @author ronglexie* @version 2018/9/1*/private int getBalanceFactor(Node node){if (node == null) {return 0;}return getHeight(node.left) - getHeight(node.right);}/*** 查看AVL平衡二叉树是否是二分搜索树** @param* @return boolean* @author ronglexie* @version 2018/9/1*/private boolean isBinarySearchTree(){ArrayList<K> keys = new ArrayList<>();inOrder(root,keys);for (int i = 1; i < keys.size(); i++) {if(keys.get(i - 1).compareTo(keys.get(i)) > 0){return false;}}return true;}/*** 查看AVL平衡二叉树是否是平衡二叉树** @return boolean* @author ronglexie* @version 2018/9/1*/private boolean isBalanced(){return isBalanced(root);}/*** 递归查看以node为根节点的AVL平衡二叉树是否是平衡二叉树** @param node* @return boolean* @author ronglexie* @version 2018/9/1*/private boolean isBalanced(Node node){if (node == null) {return true;}int balanceFactor = getBalanceFactor(node);if(Math.abs(balanceFactor) > 1){return false;}return isBalanced(node.left) && isBalanced(node.right);}// 对节点y进行向右旋转操作，返回旋转后新的根节点x//        y                              x//       / \                           /   \//      x   T4     向右旋转 (y)        z     y//     / \       - - - - - - - ->    / \   / \//    z   T3                       T1  T2 T3 T4//   / \// T1   T2/*** 右旋转操作* @param y* @return AVLTree<K,V>.Node* @author ronglexie* @version 2018/9/1*/private Node rightRotate(Node y){Node x = y.left;Node T3 = x.right;//右旋转操作x.right = y;y.left = T3;//更新heighty.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;return x;}// 对节点y进行向左旋转操作，返回旋转后新的根节点x//    y                             x//  /  \                          /   \// T1   x      向左旋转 (y)       y     z//     / \   - - - - - - - ->   / \   / \//   T2  z                     T1 T2 T3 T4//      / \//     T3 T4/*** 左旋转操作** @param y* @return AVLTree<K,V>.Node* @author ronglexie* @version 2018/9/1*/private Node leftRotate(Node y){Node x = y.right;Node T2 = x.left;//左旋转操作x.left = y;y.right = T2;//更新heighty.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;return x;}/*** 中序遍历以node为根节点的AVL平衡二叉树* 深度优先遍历，递归实现** @param node* @return void* @author ronglexie* @version 2018/8/18*/private void inOrder(Node node, ArrayList<K> keys){if(node == null){return;}inOrder(node.left,keys);keys.add(node.key);inOrder(node.right,keys);}/*** 向AVL平衡二叉树中插入元素** @param key* @param value* @return void* @author ronglexie* @version 2018/9/1*/public void add(K key, V value) {root = add(root,key,value);}/*** 向node为根元素的AVL平衡二叉树中插入元素* 递归算法** @param node* @param key* @param value* @return void* @author ronglexie* @version 2018/8/19*/private Node add(Node node, K key, V value){//递归终止条件，返回结果为nullif(node == null){size ++;return new Node(key,value);}if(key.compareTo(node.key) < 0){node.left = add(node.left,key,value);}else if(key.compareTo(node.key) > 0){node.right = add(node.right,key,value);}else {node.value = value;}/**========== 维护平衡 Start ==========*///更新Heightnode.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));//计算平衡因子int balanceFactor = getBalanceFactor(node);//LL左孩子节点的左侧产生不平衡if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){//右旋转操作return rightRotate(node);}//RR右孩子节点的右侧产生不平衡if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0){//左旋转操作return leftRotate(node);}//LR左孩子节点的右侧产生不平衡if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){node.left = leftRotate(node.left);//右旋转操作return rightRotate(node);}//RL右孩子节点的左侧产生不平衡if(balanceFactor <-1 && getBalanceFactor(node.right) > 0){node.right = rightRotate(node.right);//右旋转操作return leftRotate(node);}/**========== 维护平衡 End ==========*/return node;}/*** 查找AVL平衡二叉树的最小值** @param* @return V* @author ronglexie* @version 2018/8/18*/public V minimum(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return minimum(root).value;}/*** 查找以node为根节点AVL平衡二叉树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node minimum(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.left == null){return node;}return minimum(node.left);}/*** 查找AVL平衡二叉树的最大值** @param* @return V* @author ronglexie* @version 2018/8/18*/public V maximize(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return maximize(root).value;}/*** 查找以node为根节点AVL平衡二叉树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node maximize(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.right == null){return node;}return minimum(node.right);}/*** 删除AVL平衡二叉树的最大值** @param* @return V* @author ronglexie* @version 2018/8/18*/public V removeMax(){V maximize = maximize();removeMax(root);return maximize;}/*** 删除以node为根的AVL平衡二叉树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node removeMax(Node node){if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}node.right = removeMin(node.right);return node;}/*** 删除AVL平衡二叉树的最小值** @param* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/public V removeMin(){V minimum = minimum();removeMin(root);return minimum;}/*** 删除以node为根的AVL平衡二叉树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}public V remove(K key) {Node node = getNode(root,key);if(node != null){root = remove(root, key);return node.value;}return null;}/*** 删除以node为根的AVL平衡二叉树中的指定元素* 深度优先遍历，递归实现** @param node* @param key* @return BinarySearchTree<E>.Node* @author ronglexie* @version 2018/8/18*/private Node remove(Node node, K key) {if(node == null){return null;}Node resultNode;if(key.compareTo(node.key) < 0){node.left = remove(node.left, key);resultNode = node;}else if(key.compareTo(node.key) > 0){node.right = remove(node.right, key);resultNode = node;}else /*if(key.compareTo(node.key) == 0)*/{// 删除右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;resultNode = leftNode;}// 删除左子树为空的情况else if(node.left == null){Node rightNode = node.right;node.right = null;size --;resultNode = rightNode;}// 删除左子树、右子树均不为空的情况else {// 1、删除后用后继节点替代该位置(后继节点即待删除节点右子树中的最小节点)// 获得后继节点Node successor = minimum(node.right);// 删除后继节点，并让待删除节点的右子树成为后继节点的右子树successor.right = remove(node.right,successor.key);// 让待删除节点的左子树成为后继节点的左子树successor.left = node.left;// 将待删除节点的左、右子节点置为空node.left = node.right = null;resultNode = successor;/**// 2、删除后用前驱节点替代该位置(前驱节点即待删除节点左子树中的最大节点)// 获得前驱节点Node predecessor = maximize(node.left);// 删除前驱节点，并让待删除节点的左子树成为前驱节点的左子树predecessor.left = removeMax(node);// 让待删除节点的右子树成为前驱节点的右子树predecessor.right = node.right;// 将待删除节点的左、右子节点置为空node.left = node.right = null;return predecessor;*/}}/**========== 维护平衡 Start ==========*/if(resultNode == null){return null;}//更新HeightresultNode.height = 1 + Math.max(getHeight(resultNode.left), getHeight(resultNode.right));//计算平衡因子int balanceFactor = getBalanceFactor(resultNode);//LL左孩子节点的左侧产生不平衡if(balanceFactor > 1 && getBalanceFactor(resultNode.left) >= 0){//右旋转操作return rightRotate(resultNode);}//RR右孩子节点的右侧产生不平衡if (balanceFactor < -1 && getBalanceFactor(resultNode.right) <= 0){//左旋转操作return leftRotate(resultNode);}//LR左孩子节点的右侧产生不平衡if(balanceFactor > 1 && getBalanceFactor(resultNode.left) < 0){resultNode.left = leftRotate(resultNode.left);//右旋转操作return rightRotate(resultNode);}//RL右孩子节点的左侧产生不平衡if(balanceFactor <-1 && getBalanceFactor(resultNode.right) > 0){resultNode.right = rightRotate(resultNode.right);//右旋转操作return leftRotate(resultNode);}/**========== 维护平衡 End ==========*/return resultNode;}public boolean contains(K key) {return getNode(root,key) != null;}public V get(K key) {Node node = getNode(root, key);return node != null ? node.value : null;}public void set(K key, V value) {Node node = getNode(root, key);if(node == null){throw new IllegalArgumentException("Set failed. key is not exists!");}node.value = value;}public int getSize() {return size;}public boolean isEmpty() {return size == 0;}/*** 根据key获取Node** @param node* @param key* @return map.LinkedListMap<K,V>.Node* @author ronglexie* @version 2018/8/19*/public Node getNode(Node node,K key){if(node == null){return null;}if(key.compareTo(node.key) == 0){return node;}else if(key.compareTo(node.key) < 0){return getNode(node.left,key);}else{return getNode(node.right,key);}}/*** 节点类** @author ronglexie* @version 2018/8/18*/private class Node{public K key;public V value;public Node left,right;public int height;public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;height = 1;}}public static void main(String[] args) {ArrayList<String> words = new ArrayList<>();FileOperation.readFile("D:\\iProgramming\\Projects\\IntelliJ IDEA\\Play-with-Data-Structures-Ronglexie\\12-AVL-Tree\\src\\pride-and-prejudice.txt",words);System.out.println("Total words: " + words.size());AVLTree<String,Integer> wordsMap = new AVLTree();for (String word : words) {if(wordsMap.contains(word)){wordsMap.set(word,wordsMap.get(word)+1);}else {wordsMap.add(word,1);}}System.out.println("Total different words: " + wordsMap.getSize());System.out.println("Frequency of PRIDE "+wordsMap.get("pride"));System.out.println("Frequency of is "+wordsMap.get("is"));System.out.println("Frequency of of "+wordsMap.get("of"));System.out.println("isBinarySearchTree:"+wordsMap.isBinarySearchTree());System.out.println("isBalanced:"+wordsMap.isBalanced());for (String word : words) {wordsMap.remove(word);if(!wordsMap.isBinarySearchTree() || !wordsMap.isBalanced()){throw new RuntimeException("Error");}}}
}

AVLTreeSet.java

package set;/*** 利用AVL平衡二叉树实现集合* 不包含重复元素** @author ronglexie* @version 2018/9/1*/
public class AVLTreeSet<E extends Comparable<E>> implements Set<E> {AVLTree<E,Object> avlTree;public AVLTreeSet() {avlTree = new AVLTree<>();}@Overridepublic void add(E e) {avlTree.add(e, null);}@Overridepublic void remove(E e) {avlTree.remove(e);}@Overridepublic boolean contains(E e) {return avlTree.contains(e);}@Overridepublic int getSize() {return avlTree.getSize();}@Overridepublic boolean isEmpty() {return avlTree.isEmpty();}
}

三、基于链表实现的Set

LinkedList.java

package set;/*** 链表* 包含头指针、虚拟节点** @author ronglexie* @version 2018/8/11*/
public class LinkedList<E> {/** 虚拟头节点*/private Node dummyHead;/** 链表大小*/private int size;public LinkedList() {dummyHead = new Node(null,null);size = 0;}public int getSize(){return size;}public boolean isEmpty(){return size == 0;}/*** 向链表指定位置添加元素** @param index* @param e* @return void* @author ronglexie* @version 2018/8/12*/public void add(int index, E e){if(index < 0 || index > size){throw new IllegalArgumentException("Add faild. Illegal index.");}Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}prev.next = new Node(e,prev.next);size ++;}/*** 向链表头添加元素** @param e* @return void* @author ronglexie* @version 2018/8/12*/public void addFirst(E e){add(0,e);}/*** 向链表尾部添加元素** @param e* @return void* @author ronglexie* @version 2018/8/12*/public void addLast(E e){add(size,e);}/*** 获取指定位置元素** @param index* @return E* @author ronglexie* @version 2018/8/12*/public E get(int index){if(index < 0 || index > size){throw new IllegalArgumentException("Get faild. Illegal index.");}Node cur = dummyHead.next;for (int i = 0; i < index; i++) {cur = cur.next;}return cur.e;}/*** 获取链表头部的元素** @param* @return E* @author ronglexie* @version 2018/8/12*/public E getFirst(){return get(0);}/*** 获取链表尾部的元素** @param* @return E* @author ronglexie* @version 2018/8/12*/public E getLast(){return get(size);}/*** 修改指定位置的元素** @param index* @param e* @return void* @author ronglexie* @version 2018/8/12*/public void set(int index, E e){if(index < 0 || index > size){throw new IllegalArgumentException("Set failed. Illegal index.");}Node cur = dummyHead.next;for (int i = 0; i < index; i++) {cur = cur.next;}cur.e = e;}/*** 判断链表是否包含某个元素** @param e* @return boolean* @author ronglexie* @version 2018/8/12*/public boolean contains(E e){Node cur = dummyHead.next;while (cur != null){if (cur.e.equals(e)){return true;}cur = cur.next;}return false;}/*** 删除指定位置的元素** @param index* @return void* @author ronglexie* @version 2018/8/12*/public E remove(int index){if(index < 0 || index > size){throw new IllegalArgumentException("Delete failed. Illegal index.");}Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}Node delNode = prev.next;prev.next = delNode.next;delNode.next = null;size --;return delNode.e;}/*** 删除指定元素** @return void* @author ronglexie* @version 2018/8/18*/public void remove(E e){if(!contains(e)){throw new IllegalArgumentException("Delete failed. e is not exists.");}Node prev = dummyHead;while (prev.next != null){if(prev.next.e.equals(e)){break;}prev = prev.next;}if(prev.next != null){Node delNode = prev.next;prev.next = delNode.next;delNode.next = null;size --;}}/*** 删除所有的指定元素** @return void* @author ronglexie* @version 2018/8/18*/public void removeAll(E e){if(!contains(e)){throw new IllegalArgumentException("Delete failed. e is not exists.");}Node prev = dummyHead;while (prev.next != null){if(prev.next.e.equals(e)){Node delNode = prev.next;prev.next = delNode.next;delNode.next = null;size --;continue;}prev = prev.next;}}/*** 删除链表头部的元素** @param* @return E* @author ronglexie* @version 2018/8/12*/public E removeFirst(){return remove(0);}/*** 删除链表尾部的元素** @param* @return E* @author ronglexie* @version 2018/8/12*/public E removeLast(){return remove(size - 1);}@Overridepublic String toString() {StringBuilder result = new StringBuilder();result.append(String.format("LinkedList: size: %d\n",size));result.append("head ");Node cur = dummyHead.next;while (cur != null){result.append(cur+ "->");cur = cur.next;}result.append("NULL");return result.toString();}private class Node{private E e;private Node next;public Node(E e, Node next) {this.e = e;this.next = next;}public Node(E e) {this.e = e;}public Node() {this(null,null);}@Overridepublic String toString() {return e.toString();}}
}

LinkedListSet.java

package set;/*** 利用链表实现集合** @author ronglexie* @version 2018/8/18*/
public class LinkedListSet<E> implements Set<E> {private LinkedList linkedList;public LinkedListSet() {linkedList = new LinkedList();}@Overridepublic void add(E e) {if(!linkedList.contains(e)){linkedList.addFirst(e);}}@Overridepublic void remove(E e) {linkedList.remove(e);}@Overridepublic boolean contains(E e) {return linkedList.contains(e);}@Overridepublic int getSize() {return linkedList.getSize();}@Overridepublic boolean isEmpty() {return linkedList.isEmpty();}
}

这篇关于数据结构-高层数据结构：集合（Set）【元素不重复】【基于二分搜索树（有序集合O(logn)）、基于平衡二叉树（有序集合O(logn)）、基于链表（无序集合O(n)）、基于哈希表（无序集合O(n)）】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---