模拟实现LinkedList:下一篇文章
LinkedList底层是双向、不带头结点、非循环的链表
/*** LinkedList的模拟实现*单向 不带头 非循环链表实现*/
class SingleLinkedList {class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//永远指向头结点//创建链表public void createList() {ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(4);ListNode node5 = new ListNode(5);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}//显示public void display() {while (head != null) {System.out.print(head.val + " ");head = head.next;//head往后移}}//得到单链表的长度public int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}//清空public void clear() {this.head = null;}//头插法public void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}//尾插法public void addLast(int data) {ListNode cur = head;ListNode node = new ListNode(data);if (head == null) {head = node;}while (cur.next != null) {cur = cur.next;}cur.next = node;//这时cur就是尾巴节点}//在任意位置插入,第一个数据节点为0的下标public void addIndex(int index, int data) {ListNode node = new ListNode(data);int len = size();//0.判断index位置是否合法if (index < 0 || index > len) {return;//也可以抛异常}//1.先找到index-1的位置 下面有个findIndex方法ListNode cur = findIndex(index);//2.插入数据node.next = cur.next;cur.next = node;}private ListNode findIndex(int index) {ListNode cur = head;while (index - 1 != 0) {cur = cur.next;index--;}return cur;//index-1位置的节点}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key) {if(head==null){return;}if(head.val==key){head=head.next;return;}ListNode prev = searchPrev(key);if (prev== null) {System.out.println("没有这个数据");return;}ListNode del=prev.next;prev.next=del.next;}private ListNode searchPrev(int key){ListNode prev=head;while(prev.next!=null){if(prev.next.val==key){return prev;}else{prev=prev.next;}}return null;}//删除所有值为key的节点public void removeAllkey(int key) {if(head==null){return;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}if(head.val==key){head=head.next;}}
}
public class Test {public static void main(String[] args) {SingleLinkedList singleLinkedList=new SingleLinkedList();singleLinkedList.createList();singleLinkedList.display();}
}
此处只调用了createList()和display()。需要其他方法的自己可以在main中调用哦