/** * 链表的结点 * */ class Node{ Object data; //数据元素 Node next; //后驱结点 public Node() { this(null); } public Node(Object data) { this.data = data; this.next = null; } }
/** * 带头结点的链式链表,下标从0开始; * */ public class SinglyLinkedList<E>{ Node head; //头结点 int size; //链表的大小 public SinglyLinkedList() { head = new Node(); size = 0; } public SinglyLinkedList(E[] datas) { int n = datas.length; head = new Node(); Node p = head; for(int i=0; i<n; i++) { p.next = new Node(datas[i]); p = p.next; } size = n; } public SinglyLinkedList(SinglyLinkedList list) { head = list.head; size = list.size(); } public void add(Object e) { Node p; if(0 == size) { p = head; } else { p = index(size-1); } p.next = new Node(e); size ++; } public void concat(SinglyLinkedList list) { Node lastNode = this.index(size - 1); lastNode.next = list.index(0); size += list.size(); } public void clear() { head.next = null; size = 0; } public Object get(int i) { Node p = index(i); return p.data; } private Node index(int i) { Node p = null; if(i>=0 && i<size){ p = head; for(int j=0; j<=i; j++) { p = p.next; } } return p; } public int indexOf(Object e) { Node p = head.next; int i = 0; while(!p.data.equals(e)) { p = p.next; i++; } if(i<size) return i; else return -1; } public void insert(int i, Object e) { Node p = index(i); Node p2 = new Node(e); p2.next = p.next; p.next = p2; size ++; } public boolean isEmpty() { if(size ==0) return true; else return false; } public int lastIndexOf(Object e) { int i = size-1; while(!get(i).equals(e)) { i--; } if(i>=0) return i; else return -1; } public void remove(int i) { if(i>=0 && i<size) { Node p = null; if(i == 0) p = head; else { p = index(i-1); } p.next = index(i).next; } size --; } public void set(int i, Object e) { Node p = index(i); p.data = e; } public int size() { return size; } @Override public boolean equals(Object obj) { SinglyLinkedList list = (SinglyLinkedList)obj; if(this == obj && size == list.size) { return true; } return false; }
/** * 测试线性表 * @param args */ public static void main(String args[]) { //List list = new LinkList(); //List list = new DoubleLinkList(); SinglyLinkedList list1 = new SinglyLinkedList(); for(int i=0; i<10; i++) { list1.add(new Integer(i)); } Integer [] a = {101, 102, 103, 104, 105, 106, 107, 108, 109, 110}; SinglyLinkedList list = new SinglyLinkedList(a); list.remove(9); System.out.print("size:" + list.size() + " "); System.out.println("isEmpty:" + list.isEmpty()); System.out.print("第7个位置的元素:" + list.get(7) + " "); list.concat(list1); for(int i=0; i<list.size(); i++) { System.out.print(list.get(i) + " "); } list.add(21); list.add(22); list.insert(3, new Integer(5)); System.out.print("size:" + list.size() + " "); System.out.print("第一次出现5的索引:" + list.indexOf(5) + " "); System.out.print("最后一次出现5的索引:" + list.lastIndexOf(5) + " "); list.set(0, new Integer(30)); for(int i=0; i<list.size(); i++) { System.out.print(list.get(i) + " "); } SinglyLinkedList list2 = list; System.out.println(" is equels? " + list2.equals(list)); /** * 有序插入 * @param value 要插入的值 */ public void insertByOrder(TestList list,int value) { int j=0; //查询要插入的位置索引 if(value<=list.get(0)){ //insert方法是在索引后插入,不适合插入在第一位的 Node p = new Node(value);//新建 Node p1 = index(0); //拼接 p.next = p1; list.head.next=p; size ++; }else if(value>=list.get(list.size-1)){ j=list.size-1; }else{ for(int i=0;i<list.size;i++){ while(list.get(i)<=value&&list.get(i+1)>=value){ j=i; break; } } } if(j!=0){ insert(j, value); } } } }
带头结点链表的好处
1、防止单链表是空的而设的.当链表为空的时候,带头结点的头指针就指向头结点.如果当链表为空的时候,单链表没有带头结点,那么它的头指针就为NULL.
2、是为了方便单链表的特殊操作,插入在表头或者删除第一个结点.这样就保持了单链表操作的统一性!
3、单链表加上头结点之后,无论单链表是否为空,头指针始终指向头结点,因此空表和非空表的处理也统一了,方便了单链表的操作,也减少了程序的复杂性和出现bug的机会。
4、对单链表的多数操作应明确对哪个结点以及该结点的前驱。不带头结点的链表对首元结点、中间结点分别处理等;而带头结点的链表因为有头结点,首元结点、中间结点的操作相同 ,从而减少分支,使算法变得简单 ,流程清晰。对单链表进行插入、删除操作时,如果在首元结点之前插入或删除的是首元结点,不带头结点的单链表需改变头指针的值,在C 算法的函数形参表中头指针一般使用指针的指针(在C+ +中使用引用 &);而带头结点的单链表不需改变头指针的值,函数参数表中头结点使用指针变量即可。