数据结构链表

数据结构 链表

链表

1）链表的概念及结构:
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
2）实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向、双向带头、不带头循环、非循环组合成的。我门需要掌握的为无头单向非循环链表和无头双向链表。
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
在这里插入图片描述
无头双向链表

链表的实现

java">// 1、无头单向非循环链表实现
public class SingleLinkedList {//头插法
public void addFirst(int data);//尾插法
public void addLast(int data);//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);//删除第一次出现关键字为key的节点
public void remove(int key);//删除所有值为key的节点
public void removeAllKey(int key);//得到单链表的长度
public int size();public void display();public void clear();}

代码如下

java">public class MySingleList implements IList{//节点的内部类static 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(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head=node1;}@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);if(this.head==null){this.head= node;}else{node.next = this.head;this.head=node;}}@Overridepublic void addLast(int data) {ListNode cur = this.head;ListNode node  = new ListNode(data);if(this.head==null){this.head = node;}else{while(cur.next!=null){cur = cur.next;}cur.next = node;}}@Overridepublic void addIndex(int index, int data) throws ArithmeticException{//自定义异常if(index<0||index>size()){throw new ArithmeticException("抛出下标"+index+"异常");}if (index == 0) {addFirst(data);return;}if (index == size()) {addLast(data);return;}ListNode cur = searchPrev(index);ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}private ListNode searchPrev(int index){ListNode cur = this.head;int count = 0;while(index-1!=count){cur= cur.next;index--;}return cur;}@Overridepublic boolean contains(int key) {ListNode cur = this.head;while(cur!=null){if(cur.val==key){return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(this.head==null){//一个节点都没有return;}if(this.head.val==key){this.head = this.head.next;return;}//1.找到前驱ListNode cur = findPrev(key);//2.判断返回值是否为空if(cur==null){System.out.println("没有你要删除的元素");return;}//3.删除操作ListNode del = cur.next;cur.next = del.next;}//找到关键字key前一个地址private ListNode findPrev(int key){ListNode cur = this.head;while(cur.next!=null){if(cur.next.val==key){return cur;}cur = cur.next;}return null;}@Overridepublic void removeAllKey(int Key) {if (this.head == null) {return;}ListNode prev = head;ListNode cur = head.next;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;}}@Overridepublic int size() {int count = 0;ListNode cur = this.head;while(cur!=null){count++;cur = cur.next;}return count;}@Overridepublic void clear() {}@Overridepublic void display() {ListNode cur = this.head;while(cur!=null){System.out.println(cur.val +" ");cur = cur.next;}}}