Java Data Structure Linked List Stack Queue Tree Implementation Method Example
- 2021-07-03 00:08:54
- OfStack
This paper describes the implementation method of linked list, stack, queue and tree of Java data structure with examples. Share it for your reference, as follows:
Recently, I accidentally turned to a book, and wrote a few lines of code to realize several commonly used data structures for later investigation.
1. Linear list (linked list)
1. Node definition
/** Linked list node definition
* @author colonel
*
*/
class Node {
public int data;
Node next=null;
public Node(int data){
this.data=data;
}
}
2. Linked list operation class
/** Linked list operation class
* @author colonel
*
*/
public class operateClass {
public Node headNode=null;
/* Add a bound node to the linked list
* @param data Linked list node data
*/
public Node addNode(int data){
Node newNode=new Node(data);
if (headNode==null) {
headNode=newNode;
newNode.next=null;
return headNode;
}
Node tempNode=headNode;
while (tempNode.next!=null) {
//tempNode=headNode;
tempNode=tempNode.next;
}
tempNode.next=newNode;
return headNode;
}
/** Delete Node
* @param Delete the location of the node
*
*/
public boolean delNode(int index){
if (index<1||index>length()) {
return false;
}
if (index==1) {
headNode=headNode.next;
return true;
}
Node preNode=headNode;
Node curNode=preNode.next;
int count=2;
while (curNode!=null) {
if (count==index) {
preNode.next=curNode.next;
return true;
}
preNode=curNode;
curNode=curNode.next;
count++;
}
return true;
}
/** Take the length of the linked list
* @return Returns the length of the linked list
*/
public int length(){
int length=0;
Node temp=headNode;
while (temp!=null) {
length++;
temp=temp.next;
}
return length;
}
/** Sort linked list data by value range
* @return Returns the sorted linked list header node
*/
public Node orderList(){
Node nextNode=null;
int temp=0;
Node curNode=headNode;
while (curNode.next!=null) {
nextNode=curNode.next;
while (nextNode!=null) {
if (curNode.data>nextNode.data) {
temp=curNode.data;
curNode.data=nextNode.data;
nextNode.data=temp;
}
nextNode=nextNode.next;
}
curNode=curNode.next;
}
return headNode;
}
/**
* Remove elements with duplicate range in linked list
*/
public void redRepeat(){
if (length()<=1) {
return;
}
Node curNode=headNode;
while (curNode!=null) {
Node insidNode=curNode.next;
Node insidPreNode=insidNode;
while (insidNode!=null) {
if (insidNode.data==curNode.data) {
insidPreNode.next=insidNode.next;
//return;
}
insidPreNode=insidNode;
insidNode=insidNode.next;
}
curNode=curNode.next;
}
}
/** Output all the data in the linked list in reverse order
* @param hNode Linked list header node
*/
public void reversePrint(Node hNode){
if (hNode!=null) {
reversePrint(hNode.next);
System.out.println(hNode.data);
}
}
/**
* Print values from the beginning of the node to the end of the node
*/
public void printList(){
Node tmpNode=headNode;
while (tmpNode!=null) {
System.out.println(tmpNode.data);
tmpNode=tmpNode.next;
}
}
}
2. Stack
1. The stack is realized by array, and the specific stack operation class
class MyStack<E>{
private Object[] stack;
int top=-1;
public MyStack(){
stack=new Object[10];
}
public boolean isEmpty(){
return top==0;
}
/** Pop up the top element of the stack (do not delete)
* @return
*/
public E peek(){
if (isEmpty()) {
return null;
}
return (E) stack[top];
}
/** Stack-out top element
* @return Stack top element
*/
public E pop(){
E e=peek();
stack[top]=null;
top--;
return e;
}
/** Stack pressing
* @param item Element to be pressed
* @return Returns the element to be pressed
*/
public E push(E item){
//ensureCapacity(top+1);
stack[++top]=item;
return item;
}
/** Stack full expansion
* @param size
*/
public void ensureCapacity(int size){
int len=stack.length;
if (size>len) {
int newLen=10;
stack=Arrays.copyOf(stack, newLen);
}
}
/** Returns the top element of the stack
* @return
*/
public E getTop(){
if (top==-1) {
return null;
}
return (E) stack[top];
}
}
3. Queue
The queue is implemented using a chain
1. Queue node definition
/**
* @author colonel
* Queue node definition
* @param <Elem>
*/
class queueNode<Elem>{
queueNode<Elem> nextNode=null;
Elem data;
public queueNode(Elem data){
this.data=data;
}
}
2. Queue operation class
/**
* @author colonel
* Queue operation class
* @param <Elem>
*/
class MyQueue<Elem>{
private queueNode<Elem> headNode=null;
private queueNode<Elem> tailNode=null;
private queueNode<Elem> lastNode=null;
/** Determine whether the queue is empty
* @return Return true or false
*/
public boolean isEmpty(){
return headNode==tailNode;
}
/** Entry operation
* @param data Node element value
*/
public void put(Elem data){
queueNode<Elem> newNode=new queueNode<Elem>(data);
if (headNode==null&&tailNode==null) {
headNode=tailNode=newNode;
//tailNode=headNode.nextNode;
lastNode=tailNode.nextNode;
return;
}
tailNode.nextNode=newNode;
tailNode=newNode;
lastNode=tailNode.nextNode;
//tailNode=tailNode.nextNode;
}
/** Out-of-line operation
* @return Returns an out-of-queue element
*/
public Elem pop(){
if (headNode==lastNode) {
return null;
}
queueNode<Elem> tempNode=headNode;
Elem statElem=tempNode.data;
headNode=tempNode.nextNode;
return statElem;
}
/** Returns queue length
* @return Length
*/
public int size(){
if (isEmpty()) {
return 0;
}
int length=0;
queueNode<Elem> temp=headNode;
while (temp!=null) {
length++;
temp=temp.nextNode;
}
return length;
}
}
4. 2-tree
1. Node definition
/** Tree node definition
* @author colonel
*
*/
class TreeNode{
public int data;
public TreeNode leftNode;
public TreeNode rightNode;
public TreeNode(int data){
this.data=data;
this.leftNode=null;
this.rightNode=null;
}
}
2, 2-tree operation class
/**2 Cross-sorted tree operation class
* @author colonel
*
*/
class OperateTree{
public TreeNode rootNode;
public OperateTree(){
rootNode=null;
}
/** Element insertion 2 Cross-sorted tree
* @param data Node data to be inserted
*/
public void insert(int data){
TreeNode newNode=new TreeNode(data);
if (rootNode==null) {
rootNode=newNode;
}else {
TreeNode current=rootNode;
TreeNode parent;
while (true) {
parent=current;
if (data<current.data) {
current=current.leftNode;
if (current==null) {
parent.leftNode=newNode;
return;
}
} else {
current=current.rightNode;
if (current==null) {
parent.rightNode=newNode;
return;
}
}
}
}
}
/** Build 2 Cross-sorted tree
* @param item Element array
*/
public void buildTree(int[] item){
for (int i = 0; i < item.length; i++) {
insert(item[i]);
}
}
/**
* Presequential traversal 2 Fork tree
*/
public void preOrder(TreeNode root){
if (root!=null) {
System.out.println(root.data);
preOrder(root.leftNode);
preOrder(root.rightNode);
}
}
/** Middle order traversal
* @param root
*/
public void inOrder(TreeNode root){
if (root!=null) {
inOrder(root.leftNode);
System.out.println(root.data);
inOrder(root.rightNode);
}
}
/** Post-order traversal
* @param root
*/
public void afterOrder(TreeNode root){
if (root!=null) {
afterOrder(root.leftNode);
afterOrder(root.rightNode);
System.out.println(root.data);
}
}
/**
* Sequence traversal 2 Cross-sorted tree
*/
public void layerTrave(){
if (this.rootNode==null) {
return;
}
Queue<TreeNode> myQueue=new LinkedList<>();
myQueue.add(rootNode);
while (!myQueue.isEmpty()) {
TreeNode tempNode=myQueue.poll();
System.out.println(tempNode.data);
if (tempNode.leftNode!=null) {
myQueue.add(tempNode.leftNode);
}
if (tempNode.rightNode!=null) {
myQueue.add(tempNode.rightNode);
}
}
}
STEP 5 Summarize
To better understand what data structures are, we need to continue to explore and keep in mind. by: colonel
More readers interested in java algorithm can check the topics of this site: "Java Data Structure and Algorithm Tutorial", "Java Operation DOM Node Skills Summary", "Java File and Directory Operation Skills Summary" and "Java Cache Operation Skills Summary"
I hope this article is helpful to everyone's java programming.