【数据结构与算法】java链表操作

阳光穿透心脏的1/2处 2022-08-12 00:15 231阅读 0赞

链表操作代码量少但是比较容易出错，是比较适合面试的地方。

*  代码实现

/**
     * 源码名称：MyLinkList.java 
     * 日期：2014-09-05
     * 程序功能：java链表操作 
     * 版权：CopyRight@A2BGeek 
     * 作者：A2BGeek
     */
    import java.util.Stack;
    
    public class MyLinkList {
    	class LinkNode<T> {
    		private T mValue;
    		private LinkNode<T> mNext;
    
    		public LinkNode(T value) {
    			// TODO Auto-generated constructor stub
    			mValue = value;
    		}
    
    		public void setValue(T value) {
    			mValue = value;
    		}
    
    		public T getValue() {
    			return mValue;
    		}
    
    		public void setNext(LinkNode<T> next) {
    			mNext = next;
    		}
    
    		public LinkNode<T> getNext() {
    			return mNext;
    		}
    	}
    
    	// head node
    	LinkNode<Integer> mHead = null;
    	int mSize;
    
    	// add
    	public void add(int value) {
    		LinkNode<Integer> newNode = new LinkNode<Integer>(value);
    		newNode.setNext(null);
    		if (mHead == null) {
    			mHead = newNode;
    		} else {
    			LinkNode<Integer> tmp = mHead;
    			while (tmp.getNext() != null) {
    				tmp = tmp.getNext();
    			}
    			tmp.setNext(newNode);
    		}
    		mSize++;
    	}
    
    	// insert
    	public void insert(int index, int value) {
    		LinkNode<Integer> newNode = new LinkNode<Integer>(value);
    		if (mHead == null) {
    			newNode.setNext(null);
    			mHead = newNode;
    			mSize++;
    		} else {
    			if (index > mSize - 1) {
    				System.out.println("index out of bound");
    			} else {
    				int j = 0;
    				LinkNode<Integer> tmp = mHead;
    				while (j < index) {
    					tmp = tmp.getNext();
    					j++;
    				}
    				newNode.setNext(tmp.getNext());
    				tmp.setNext(newNode);
    				mSize++;
    			}
    		}
    	}
    
    	// delete
    	public void deleteByIndex(int index) {
    		if (mHead == null) {
    			System.out.println("linklist empty");
    		} else {
    			if (index > mSize - 1) {
    				System.out.println("index out of bound");
    			} else if (index == 0) {
    				mHead = mHead.getNext();
    			} else {
    				int j = 0;
    				LinkNode<Integer> pretmp = mHead;
    				while (j < index - 1) {
    					pretmp = pretmp.getNext();
    					j++;
    				}
    				pretmp.setNext(pretmp.getNext().getNext());
    			}
    		}
    	}
    
    	public void deleteByValue(int value) {
    		if (mHead == null) {
    			System.out.println("linklist empty");
    		} else {
    			LinkNode<Integer> pretmp = null;
    			LinkNode<Integer> tmp = mHead;
    			while (tmp != null) {
    				if (tmp.getValue() != value) {
    					pretmp = tmp;
    					tmp = tmp.getNext();
    				} else {
    					break;
    				}
    			}
    			if (tmp == null) {
    				System.out.println("not found");
    			} else if (pretmp == null) {
    				mHead = tmp.getNext();
    			} else {
    				pretmp.setNext(tmp.getNext());
    			}
    		}
    
    	}
    
    	// reverse
    	public void reverse() {
    		LinkNode<Integer> tmp = mHead;
    		LinkNode<Integer> pretmp = null;
    		LinkNode<Integer> nexttmp = null;
    		while (tmp != null) {
    			nexttmp = tmp.getNext();
    			tmp.setNext(pretmp);
    			pretmp = tmp;
    			tmp = nexttmp;
    		}
    		mHead = pretmp;
    	}
    
    	// print_recursive
    	public void printR(LinkNode<Integer> start) {
    		if (start == null) {
    			return;
    		} else {
    			System.out.print(start.getValue() + " ");
    			printR(start.getNext());
    		}
    	}
    
    	// print_norecursive
    	public void printNor(LinkNode<Integer> start) {
    		if (start == null) {
    			System.out.println("linklist empty");
    		} else {
    			LinkNode<Integer> tmp = start;
    			while (tmp != null) {
    				System.out.print(tmp.getValue() + " ");
    				tmp = tmp.getNext();
    			}
    		}
    	}
    
    	// printreverse_recursive
    	public void printRR(LinkNode<Integer> start) {
    		if (start == null) {
    			return;
    		} else {
    			printRR(start.getNext());
    			System.out.print(start.getValue() + " ");
    		}
    	}
    
    	// printreverse_norecursive
    	public void printRNor(LinkNode<Integer> start) {
    		if (start == null) {
    			System.out.println("linklist empty");
    		} else {
    			Stack<LinkNode<Integer>> stack = new Stack<LinkNode<Integer>>();
    			LinkNode<Integer> tmp = start;
    			while (tmp != null) {
    				stack.push(tmp);
    				tmp = tmp.getNext();
    			}
    			while (!stack.isEmpty()) {
    				System.out.print(stack.pop().getValue() + " ");
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		MyLinkList myLinkList = new MyLinkList();
    		myLinkList.add(1);
    		myLinkList.add(2);
    		myLinkList.add(3);
    		myLinkList.add(4);
    		myLinkList.add(5);
    		myLinkList.insert(3, 6);
    		System.out.println("linklist size is " + myLinkList.mSize);
    		myLinkList.printR(myLinkList.mHead);
    		System.out.println();
    		myLinkList.deleteByIndex(0);
    		myLinkList.printNor(myLinkList.mHead);
    		System.out.println();
    		// myLinkList.reverse();
    		// myLinkList.printRR(myLinkList.mHead);
    		// System.out.println();
    		// myLinkList.printRNor(myLinkList.mHead);
    	}
    }