文章出處
鏈表是一種遞歸的數據結構，它或者為null，或者是指向一個節點的引用，該節點含有一個泛型的元素和一個指向另一條鏈表的引用。在鏈表頭部插入元素，插入的原始最后出現在鏈表的首部；在鏈表尾部插入元素，插入的元素最后出現在鏈表的尾部；刪除鏈表中間部分的節點，則需要遍歷鏈表（左向右是首到尾）。
一般在某個數據結構類的內部定義一個表示鏈表節點的內部類：
private static class Node{ private T item; private Node next; }
背包基本實現：
/** * 背包是一種不支持從中刪除元素的集合數據類型，它的目的就是幫助用例收集元素并迭代遍歷所有收集到的元素，鏈表實現 * * @author xzm * * @param*/public class BagMain implements Iterable { //實現Iterable接口允許我們使用增強for循環遍歷元素 /** * 數據域、指針域 * @author xzm * */ private static class Node { private T item; private Node next; } private int count; private Node first; public BagMain() { first = null; count = 0; } /** * 表頭出插入一個節點 * @param item */ public void add(T item) { Node oldlast = first; first = new Node (); first.item = item; first.next = oldlast; count++; } public boolean isEmpty() { return first == null; } public int size() { return count; } @Override public Iterator iterator() { // TODO Auto-generated method stub return new BagIterator(); } private class BagIterator implements Iterator { private Node current = first; @Override public boolean hasNext() { return current != null; } @Override public T next() { T item = current.item; current = current.next; return item; } }}
隊列基本實現：
/** * 先進先出隊列是一種基于先進先出策略的集合模型，在表尾插入元素 * * @author xzm * */public class QueueMainimplements Iterable { private Node head;// 表頭節點 private Node tail;// 表尾節點 private int count; private static class Node { private T item; private Node next; } public QueueMain() { head = null; tail = null; count = 0; } /** * 隊列尾部添加元素 * * @param item */ public void enqueue(T item) { Node oldlast = tail; tail = new Node (); tail.item = item; tail.next = null; if (isEmpty()) head = tail; else oldlast.next = tail; count++; } /** * 隊列頭部刪除最早添加的元素 * * @return */ public T dequeue() { T item = head.item; head = head.next; if (isEmpty()) tail = null; count--; return item; } public boolean isEmpty() { return head == null; } public int size() { return count; } @Override public Iterator iterator() { return new QueueIterator(); } private class QueueIterator implements Iterator { private Node current = head; @Override public boolean hasNext() { return current != null; } @Override public T next() { T item = current.item; current = current.next; return item; } }}
棧基本實現：
/** * 棧是一種基于先進后出策略的集合模型,在表頭插入元素 * * @author xzm * */public class StackMainimplements Iterable { private Node head; // 表頭節點 private int count; private static class Node { private T item; private Node next; } public StackMain() { head = null; count = 0; } /** * 表頭添加一個元素 */ public void push(T item) { Node oldhead = head; head = new Node (); head.item = item; head.next = oldhead; count++; } /** * 刪除最近添加的元素 * * @return */ public T pop() { T item = head.item; head = head.next; count--; return item; } public boolean isEmpty() { return head == null; } public int size() { return count; } @Override public Iterator iterator() { return new StackIterator(); } private class StackIterator implements Iterator { private Node currnet = head; @Override public boolean hasNext() { return currnet != null; } @Override public T next() { T item = currnet.item; currnet = currnet.next; return item; } }}
雙向鏈表基本實現：
/** * 雙向鏈表 * * @author xzm * * @param*/public class BidirectionalLinkedListMain implements Iterable { private DoubleNode head; private DoubleNode tail; private int count; private static class DoubleNode { private T item; private DoubleNode previousNode; // 前驅節點 private DoubleNode posteriorNode; // 后驅節點 } public BidirectionalLinkedListMain() { head = null; tail = null; count = 0; } /** * 首部插入元素 * * @param item */ public void insertAtHead(T item) { DoubleNode oldhead = head; head = new DoubleNode<>(); head.item = item; head.posteriorNode = oldhead; head.previousNode = null; if (isEmpty()) { tail = head; } else if (oldhead != null) { oldhead.previousNode = head; } count++; } /** * 尾部插入元素 * * @param item */ public void insertAtTail(T item) { DoubleNode oldtail = tail; tail = new DoubleNode<>(); tail.item = item; tail.posteriorNode = null; tail.previousNode = oldtail; if (isEmpty()) head = tail; else if (oldtail != null) { oldtail.posteriorNode = tail; } count++; } /** * 首部刪除元素 * * @return * @throws NoElementException */ public T delectAtHead() throws NoElementException { if (count <= 0) throw new NoElementException("鏈表中沒有元素，首部刪除失敗"); T item = head.item; if (size() == 1) { System.out.println("鏈表中只有一個元素"); tail = head = null; } else { DoubleNode newhead = head.posteriorNode; newhead.previousNode = null; head.posteriorNode = null; head = newhead; } count--; return item; } /** * 尾部刪除元素 * * @return * @throws NoElementException */ public T delectAtTail() throws NoElementException { if (count <= 0) throw new NoElementException("鏈表中沒有元素，尾部刪除失敗"); T item = tail.item; if (size() == 1) { System.out.println("鏈表中只有一個元素"); head = tail = null; } else { DoubleNode newtail = tail.previousNode; newtail.posteriorNode = null; tail.previousNode = null; tail = newtail; } count--; return item; } /** * 在某個節點之前插入元素，注意更新在首部插入節點時，更新head指針 * * @param data * 節點的值 * * @param insertItem * 插入的值 * @throws NoElementException */ public boolean insertBeforeNode(T data, T insertItem) throws NoElementException { if (count <= 0) throw new NoElementException("鏈表中沒有元素，插入失敗"); DoubleNode other = head; while (other != null) { if (other.item.equals(data)) { DoubleNode insert = new DoubleNode<>(); insert.item = insertItem; insert.posteriorNode = other; insert.previousNode = other.previousNode; other.previousNode = insert; if (insert.previousNode != null) { insert.previousNode.posteriorNode = insert; } else head = insert; count++; return true; } other = other.posteriorNode; } System.out.println("沒有找到值為" + data + "的節點，插入失敗"); return false; } /** * 在某個節點之前插入元素，注意在尾部插入節點時，更新tail指針 * * @param data * 節點的值 * * @param insertItem * 插入的值 * @throws NoElementException */ public boolean insertAfterNode(T data, T insertItem) throws NoElementException { if (count <= 0) throw new NoElementException("鏈表中沒有元素，插入失敗"); DoubleNode other = head; while (other != null) { if (other.item.equals(data)) { DoubleNode insert = new DoubleNode<>(); insert.item = insertItem; insert.previousNode = other; insert.posteriorNode = other.posteriorNode; other.posteriorNode = insert; if (insert.posteriorNode != null) insert.posteriorNode.previousNode = insert; else tail = insert; count++; return true; } other = other.posteriorNode; } System.out.println("沒有找到值為" + data + "的節點，插入失敗"); return false; } /** * 刪除某個節點 * * @param data * 節點的值，從鏈表首部開始計算 * @throws NoElementException */ public boolean delectNode(int data) throws NoElementException { if (count <= 0) throw new NoElementException("鏈表中沒有元素,無法刪除元素"); DoubleNode other = head; while (other != null) { if (other.item.equals(data)) { if(size() == 1){ tail = head = null; }else if (other.previousNode == null) { DoubleNode newhead = head.posteriorNode; newhead.previousNode = null; other.posteriorNode = null; head = newhead; } else if (other.posteriorNode == null) { DoubleNode newtail = other.previousNode; newtail.posteriorNode = null; other.previousNode = null; tail = newtail; } else { other.previousNode.posteriorNode = other.posteriorNode; other.posteriorNode.previousNode = other.previousNode; other.previousNode = null; other.posteriorNode = null; } count--; return true; } other = other.posteriorNode; } System.out.println("沒有找到值為" + data + "的節點，刪除失敗"); return false; } public boolean isEmpty() { return count == 0; } public int size() { return count; } @Override public Iterator iterator() { return new BidirectionalIterator(); } private class BidirectionalIterator implements Iterator { private DoubleNode current = head; @Override public boolean hasNext() { return current != null; } @Override public T next() { T item = current.item; current = current.posteriorNode; return item; } }}
雙向鏈表基本測試代碼：
BidirectionalLinkedListMainlistMain = new BidirectionalLinkedListMain<>();System.out.println("首部插入1");listMain.insertAtHead(1);System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());for (Integer integer : listMain) {System.out.print(" " + integer);}System.out.println();System.out.println("尾部插入3");listMain.insertAtTail(3);System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());for (Integer integer : listMain) {System.out.print(" " + integer);}System.out.println();System.out.println("在3之后插入4");listMain.insertAfterNode(3, 4);System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());for (Integer integer : listMain) {System.out.print(" " + integer);}System.out.println();System.out.println("3之前插入5");listMain.insertBeforeNode(3,5);System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());for (Integer integer : listMain) {System.out.print(" " + integer);}System.out.println();System.out.println("刪除4");listMain.delectNode(4);System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());for (Integer integer : listMain) {System.out.print(" " + integer);}System.out.println();
輸出結果：
測試雙向鏈表首部插入1isEmpyt: false size: 1 1尾部插入3isEmpyt: false size: 2 1 3在3之后插入4isEmpyt: false size: 3 1 3 43之前插入5isEmpyt: false size: 4 1 5 3 4刪除4isEmpyt: false size: 3 1 5 3
以上。就愛閱讀www.92to.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161206/63486.html
文章列表
全站熱搜
留言列表
