数据结构-------单链表
单链表：
在计算机科学中，链表是数据元素的线性组合，元素储存上并不连续。
可以分为：单向链表、双向链表、循环链表
单向链表：
首先，定义结点的类型，它包括值和下一个结点。
头部插入法:
相关java代码:
1 private Node head;//定义头部结点 2 public class Node{ 3 private int value;//每个结点的值 4 private Node next;//指向下一个结点 5 public Node(int value,Node next) { 6 this.value=value; 7 this.next=next; 8 } 9 } 10 //实现添加元素的方法 11 public void addFirwst(int value) { 12 // head = new Node(value,null) ;//假设链表为空,也就是head为空 这一行代码和下一行代码功能一样 head为空那么new Node(value,head) 13 head = new Node(value,head);//假设链表不为空 14 } 15 //while循环遍历元素loop 16 public void loop1() { 17 Node p = head; 18 while(p!=null) { 19 System.out.print(p.value+"\t"); 20 p=p.next; 21 } 22 }
相关测试代码:
1 SingleLinkList singlelinklist = new SingleLinkList(); 2 singlelinklist.addFirwst(6); 3 singlelinklist.addFirwst(2); 4 singlelinklist.addFirwst(8); 5 singlelinklist.addFirwst(12); 6 singlelinklist.addFirwst(0); 7 System.out.println("遍历元素loop1:"); 8 singlelinklist.loop1();
结果显示:
各种遍历方法:
除了上述代码中的while循环还有for循环和迭代器和Consumer等方法
//for循环遍历元素 public void loop2() { for(Node p=head;p!=null;p=p.next) { System.out.print(p.value+"\t"); } } //通过Consumer来遍历元素 public void loop3(Consumer<Integer> consumer) { for(Node p=head;p!=null;p=p.next) { consumer.accept(p.value); } } //通过迭代器来遍历元素 @Override public Iterator<Integer> iterator() { // TODO Auto-generated method stub return new Iterator<Integer>() { Node p =head; @Override public boolean hasNext() { // TODO Auto-generated method stub return p!=null; } @Override public Integer next() { // TODO Auto-generated method stub int value = p.value; p=p.next; return value; } }; }
尾部插入法：
1 //尾插法 尾部插入 主要找到尾部最后一个元素 2 private Node findLast() { 3 if(head==null) { 4 return null; 5 } 6 Node p; 7 for(p=head;p.next!=null;p=p.next) { 8 9 } 10 return p; 11 } 12 public void addLast(int value) { 13 Node last = findLast();//找到最后一个元素 14 if(last==null) { 15 addFirwst(value); 16 return; 17 } 18 last.next = new Node(value,null); 19 }
效果
根据索引值求返回值：
1 //根据索引求返回值 2 private Node findNode(int index) { 3 int i=0; 4 Node p; 5 for(p=head;p!=null;p=p.next,i++) { 6 if(i==index) { 7 return p; 8 } 9 } 10 return null; 11 } 12 public int get(int index) { 13 Node p = findNode(index); 14 if(p==null) { 15 throw new IllegalArgumentException(String.format("index [%d] 不合法", index)); 16 } 17 return p.value; 18 }
根据索引值添加元素：
1 //给出索引添加元素 2 public void insert(int index,int value) { 3 if(index==0) { 4 addFirwst(value); 5 return; 6 } 7 Node prev = findNode(index-1);//找到当前元素的前一个元素 8 if(prev==null) { 9 throw new IllegalArgumentException(String.format("index [%d] 不合法", index)); 10 } 11 prev.next = new Node(value,prev.next); 12 13 }
删除第一个元素：
1 //删除第一个元素 2 public void removeFirst() { 3 if(head==null) { 4 throw new IllegalArgumentException(String.format("index [%d] 不合法")); 5 } 6 head = head.next; 7 }
根据索引删除元素：
1 //根据索引删除元素 2 public void remove(int index) { 3 //根据index-1前面一个元素 4 if(index==0) { 5 removeFirst(); 6 } 7 Node prev = findNode(index-1); 8 if(prev==null) { 9 throw new IllegalArgumentException(String.format("index [%d] 不合法")); 10 } 11 Node removed = prev.next; 12 if(removed==null) { 13 throw new IllegalArgumentException(String.format("index [%d] 不合法")); 14 } 15 prev.next = removed.next; 16 17 }