Reversing and Removing Nodes in an Integer Linked List
Added on 2019-10-18
6 Pages2157 Words149 Views
|
|
|
ublic class IntList { // The space allocated for the arrays that store the nodes. Each node will // consist of an int key and a successor, stored in two arrays to minimize // memory overhead. private static int SPACE; // The keys stored in the individual nodes. private static int[] key; // The successors of the individual nodes. Value 0 denotes no successor. // Nonnegative value means that the node has been allocated, whereas a // negative value means that the node is part of the free list, with // the negation of the value being the successor node index in the free list. private static int[] next; // Position of the first free node. private static int freeHead; // Call counts for various methods. private static long getKeyCount = 0; private static long getNextCount = 0; private static long setKeyCount = 0; private static long setNextCount = 0; // Current number of allocated nodes in the list private static int allocatedNodeCount = 0; /** * Returns the current number of allocated nodes. * @return The current number of allocated nodes. */ public static int getAllocatedNodeCount() { return allocatedNodeCount; } /** * Should be called once in the beginning. Initializes the simulated node space. * @param maxn Number of total nodes to allocate space for initially. */ public static void initialize(int maxn) { SPACE = maxn; key = new int[SPACE]; next = new int[SPACE]; freeHead = 1; for(int i = 1; i < SPACE - 1; i++) { next[i] = -(i+1); } } // Verify that the node n really exists and has been allocated for use. private static void verifyIndex(int n) { if(n < 1 || n >= SPACE || next[n] < 0) { throw new IllegalStateException("Node " + n + " is not currently allocated for use."); } }
/** * Returns the key of node {@code n}. * @param n The index of node whose key is read. * @return The key of node {@code n}. */ public static int getKey(int n) { verifyIndex(n); getKeyCount++; return key[n]; } /** * Returns the successor of node {@code n}. * @param n The index of node whose successor is read. * @return The successor of node {@code n}. */ public static int getNext(int n) { verifyIndex(n); getNextCount++; return next[n]; } /** * Assigns a new key to node {@code n}. * @param n The index of node whose key is assigned. * @return The previous key of node {@code n} before this assignment. */ public static int setKey(int n, int k) { verifyIndex(n); if(lockValue != 0) { throw new IllegalStateException("Trying to modify a key while keysare locked."); } setKeyCount++; int result = key[n]; key[n] = k; return result; } /** * Assigns a new successor node to node {@code n}. * @param n The index of node whose successor is assigned. * @return The previous successor of node {@code n} before this assignment. */ public static int setNext(int n, int m) { verifyIndex(n); setNextCount++; int result = next[n]; next[n] = m; return result; } /** * Allocates a new node with the given key. * @param k The key for the new node. * @return The index of the new allocated node.
*/ public static int allocate(int k) { if(freeHead > 0) { int n = freeHead; freeHead = -next[freeHead]; next[n] = 0; key[n] = k; allocatedNodeCount++; return n; } else { throw new IllegalStateException("No more space for nodes available."); } } /** * Allocates a chain of nodes for the keys in the parameter array. * @param keys The array of keys to convert into a linked list. * @return The index of the first node of the chain. */ public static int allocate(int[] keys) { int prev = 0; for(int i = keys.length - 1; i >= 0; i--) { int n = allocate(keys[i]); setNext(n, prev); prev = n; } return prev; } /** * Releases the entire chain of nodes from the starting node. If you want to * release just one node, set its successor to 0 before calling this method. * @param n The first node of the chain to release. * @return The number of nodes that were released. */ public static int release(int n) { int count = 0; while(n != 0) { verifyIndex(n); int m = next[n]; next[n] = -freeHead; freeHead = n; n = m; allocatedNodeCount--; count++; } return count; } // The rest of this class is for demonstration purposes. Read through these methods until // you understand what they do, and then use them as models in implementing the methods in
End of preview
Want to access all the pages? Upload your documents or become a member.
Related Documents