链表一般有单向链表，双向链表和双向循环链表三种
双向链表的每一个结点有着三个主要部分：1，存储数据的数据域 2，存储前指针的指针域 3，存储后指针的指针域
1.MyList接口定义功能
1 public interface MyList{ 2 //新增一个元素 3 void add(T element); 4 //删除与输入元素相同的元素 5 void delete(T element); 6 //根据索引删除元素 7 void delete(int index); 8 //更新元素 9 void update(int index,T newelement);10 //查询111 boolean contains(T element);12 13 T at(int index);14 15 int indexOf(T element);16 }
2.ListNode结点类
1 public class ListNode{ 2 T data; 3 ListNode pre; //前驱结点 4 ListNode next; //后驱结点 5 6 public ListNode() 7 { 8 9 }10 public ListNode(T element)11 {12 this.data=element;13 }14 15 16 }
3.DoubleLinkedList类
1 public class DoubleLinkedListimplements MyList { 2 private ListNode first=new ListNode (); //头结点哑元 3 private ListNode last=new ListNode (); //尾结点哑元 4 private int size=0; //记录添加的个数 5 6 public DoubleLinkedList() 7 { 8 first.next=last; 9 last.pre=first; 10 } 11 12 @Override 13 public void add(T element) { 14 ListNode newNode=new ListNode (element); 15 //注意添加结点的顺序 16 last.pre.next=newNode; 17 newNode.pre=last.pre; 18 newNode.next=last; 19 last.pre=newNode; 20 size++; 21 } 22 23 @Override 24 public void delete(T element) { 25 ListNode p=first.next; //复制一个头结点，以免后面操作影响头结点 26 while(p!=null) 27 { 28 if(p.data.equals(element)) 29 { 30 p.pre.next=p.next; 31 p.next.pre=p.pre; 32 size--; 33 return ; 34 } 35 p=p.next; 36 } 37 38 } 39 40 @Override 41 public void delete(int index) { 42 int i=0; 43 ListNode p=first.next; 44 while(p!=last) 45 { 46 if(i==index) 47 { 48 p.pre.next=p.next; 49 p.next.pre=p.pre; 50 p.pre=null; 51 p.next=null; 52 size--; 53 return ; 54 } 55 p=p.next; 56 i++; 57 } 58 59 } 60 61 @Override 62 public void update(int index, T newelement) { 63 int i=0; 64 ListNode p=first.next; 65 while(p!=null) 66 { 67 if(i==index) 68 { 69 p.data=newelement; 70 } 71 p=p.next; 72 i++; 73 } 74 75 76 } 77 78 @Override 79 public boolean contains(T element) { 80 return indexOf(element)>=0; 81 } 82 83 @Override 84 public T at(int index) { 85 int i=0; 86 ListNode p=first.next; 87 while(p!=null) 88 { 89 if(i==index) 90 { 91 return (T) p.data; 92 } 93 p=p.next; 94 i++; 95 } 96 return null; 97 } 98 99 @Override100 public int indexOf(T element) {101 int i=0;102 ListNode p=first.next;103 while(p!=null)104 {105 if(p.data.equals(element))106 {107 return i;108 }109 p=p.next;110 i++;111 }112 return -1;113 }114 115 @Override116 public String toString()117 {118 StringBuilder sb=new StringBuilder("[");119 ListNode p=first.next;120 while(p!=last)121 {122 sb.append(p.data+(p.next!=last?",":""));123 124 p=p.next;125 }126 sb.append("]");127 return sb.toString();128 }129 130 public int getSize()131 {132 return this.size;133 }134 135 136 }
单向链表：只有一个指向下一个节点的指针。
优点：单向链表增加删除节点简单。遍历时候不会死循环；
缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。
适用于节点的增加删除。
双向链表：有两个指针，一个指向前一个节点，一个后一个节点。
优点：可以找到前驱和后继，可进可退；
缺点：增加删除节点复杂，多需要分配一个指针存储空间。
适用于需要双向查找节点值的情况。