主要内容一、动态链表
1、定义2、相关名词3、注意点(java中没有指针概念)(理解内存分配)
我们来画个图(配合相应代码)理解一下
1)、链表初始化2)、添加元素3)、再添加一个元素 二、单向链表linkedSinglyList
1、添加元素
1)、当链表为空时,添加元素2)、添加到首元素时3)、添加到尾元素时4)、按索引添加到中间位置时5)、添加元素代码实现 2、删除元素
1)、删除头结点2)、删除尾结点3)、删除中间元素4)、当链表中只剩一个元素时,删除5)、删除元素代码实现 3、单链表整体代码
主要内容单向链表
单向循环链表
双向循环链表
链栈
链队列
2、相关名词为了表示每个数据元素ai与其直接后继数据元素ai+1 之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像,称为结点(Node)。
n个结点(ai的存储映像)链结成一个链表,即为线性表(a1, a2, …, an)的链.式存储结构,因为此链表的每个结点中只包含-一个指针域,所以叫做单链表。
头结点是指链表中的第一个结点,有真实头结点和虚拟头结点之分
真实头结点:其第一个结点用于存储数据(常用)
虚拟头结点:其第一个结点不许存储数据
头指针:仅仅是一个引用变量,存储头结点地址的指针而已
尾指针:同头指针,不过是链表中最后一个结点的指针而已
数据结构是灵活的,没有一定的存在,也没有一定的不存在。根据需求比如可以不要尾指针,也可以定义一个中间指针、总结点数量、最值等等,因为代码是自己写的,根据自己需求添加需要的,删除不需要的。
3、注意点(java中没有指针概念)(理解内存分配)java中是没有指针存在的,我们在java中所提到的指针只是我们逻辑上的理解,那我们是怎么实现链式存储的呢?
这里要是不细想的话,可以不用考虑
我们再次采用了内部类的方法
//概括性的举个例子,代码并不完整 public class linkedSinglyList我们来画个图(配合相应代码)理解一下 1)、链表初始化{ //定义结点对象,内部类 private class Node { E data; //数据域 Node next; //指针域 public Node() {//内部类构造函数 this.data = 1; this.next = null; } ... } public void add(int index, E element) {//添加元素方法 Node n = new Node(element); head = n; tail = n; } private Node head; //头指针,并没有开辟内存 private Node tail; //尾指针; public linkedSinglyList() {//链表构造函数 head = null; tail = null; size = 0; } ... }
//初始化构造方法 public linkedSinglyList() {//链表构造方法 head = null; tail = null; size = 0; }2)、添加元素
//调用add方法 public void add(int index, E element) {//添加元素方法 Node n = new Node(element); head = n; tail = n; } //方法里开辟了新的内存,所以先执行内部类构造函数 public Node() { this.data = 1; this.next = null; } //然后进行head和tail的赋值
这里内部类的初始化的null和链表一开始初始化的null一样的理解
3)、再添加一个元素tail.next = n;//上一步,tail是和head指向同一片空间,这一步,就是让前一个的地址域赋值新开辟的这块地址 tail = n;//再让tail指向新开辟的这块地址二、单向链表linkedSinglyList
linkedSinglyList就是线性结构链式存储方式的具体实现,称为单链表
主要的还是”增删改查“功能。先分段讲解一下
1、添加元素 1)、当链表为空时,添加元素 2)、添加到首元素时 3)、添加到尾元素时 4)、按索引添加到中间位置时需要定义一个指针,从头遍历,找到需要删除的元素
//实现代码 public void add(int index, E element) { if (index < 0 || index > size) {//index是索引,索引超过范围,将会抛出异常 throw new IllegalArgumentException("add index out of range"); } Node n = new Node(element); if (size == 0) {//当链表没有元素的时候 head = n; tail = n; } else if (index == 0) {//当添加到头结点的时候 n.next = head; head = n; } else if (index == size) {//当添加到尾节点的时候 tail.next = n; tail = n; } else {//添加到链表的中间位置,需要根据索引从头遍历 Node p = head; for (int i = 0; i < index - 1; i++) { p = p.next; } n.next = p.next; p.next = n; } size++; }2、删除元素 1)、删除头结点
定义一个指针先指向头结点,然后头结点后移,删除原来的结点
2)、删除尾结点 3)、删除中间元素直接遍历到需要删除的元素前一个位置,然后让前一个元素的指针指向下一个即可
直接让head和tail赋值为空即可
5)、删除元素代码实现public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("remove index out of range"); } E ret = null; if (size == 1) { ret = head.data; head = null; tail = null; } else if (index == 0) { Node n = head; ret = n.data; head = n.next; n.next = null; } else if (index == size - 1) { Node p = head; while (p.next != tail) { p = p.next; } ret = tail.data; p.next = null; tail = p; } else { Node p = head; for (int i = 0; i < index - 1; i++) { p = p.next; } Node n = p.next; ret = n.data; p.next = n.next; n.next = null; } size--; return ret; }
查找和修改基本上就没什么了
3、单链表整体代码package p3.链式结构; import p1.接口.List; import p2.线性结构.ArrayList; import java.util.Comparator; import java.util.Iterator; //单向链表 public class linkedSinglyListimplements List { //定义结点对象 private class Node { E data; //数据域 Node next; //指针域 public Node(){ this(null,null); } public Node(E data) { this(data,null); } public Node(E data, Node next) { this.data = data; this.next = next; } @Override public String toString() { return data.toString(); } } private Node head; //头指针 private Node tail; //尾指针 private int size; //元素的个数 public linkedSinglyList() { head = null; tail = null; size = 0; } public linkedSinglyList(E[] arr) { if (arr == null || arr.length == 0) { throw new IllegalArgumentException("arr is null"); } for (int i = 0; i < arr.length; i++) { add(arr[i]); } } @Override public void add(E element) { add(size, element); } @Override public void add(int index, E element) { if (index < 0 || index > size) { throw new IllegalArgumentException("add index out of range"); } Node n = new Node(element); if (size == 0) { head = n; tail = n; } else if (index == 0) { n.next = head; head = n; } else if (index == size) { tail.next = n; tail = n; } else { Node p = head; for (int i = 0; i < index - 1; i++) { p = p.next; } n.next = p.next; p.next = n; } size++; } @Override public void remove(E element) { int index = indexOf(element); if (index != -1) { remove(index); } } @Override public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("remove index out of range"); } E ret = null; if (size == 1) { ret = head.data; head = null; tail = null; } else if (index == 0) { Node n = head; ret = n.data; head = n.next; n.next = null; } else if (index == size - 1) { Node p = head; while (p.next != tail) { p = p.next; } ret = tail.data; p.next = null; tail = p; } else { Node p = head; for (int i = 0; i < index - 1; i++) { p = p.next; } Node n = p.next; ret = n.data; p.next = n.next; n.next = null; } size--; return ret; } @Override public E get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get index out of range"); } if (index == 0) { return head.data; } else if (index == size - 1) { return tail.data; } else { Node p = head; for (int i = 0; i < index; i++) { p = p.next; } return p.data; } } @Override public E set(int index, E element) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get index out of range"); } E ret = null; if (index == 0) { ret = head.data; head.data = element; } else if (index == size - 1) { ret = tail.data; tail.data = element; } else { Node p = head; for (int i = 0; i < index; i++) { p = p.next; } ret = p.data; p.data = element; } return ret; } @Override public int size() { return size; } @Override public int indexOf(E element) { Node p = head; int index = 0; while (!p.data.equals(element)) { p = p.next; index++; if (p == null) { return -1; } } return index; } @Override public boolean contains(E element) { return indexOf(element) != -1; } @Override public boolean isEmpty() { return size == 0 && head == null && tail == null; } @Override public void clear() { head = null; tail = null; size = 0; } @Override public void sort(Comparator c) { if (c == null) { throw new IllegalArgumentException("comparator can not be null"); } //此处的插入排序O(n^3) if (size == 0 || size == 1) { return; } Node nodeA = head; Node nodeB = nodeA.next; while (true) { while (true) { if (c.compare(nodeA.data, nodeB.data) > 0) { swap(nodeA, nodeB); } if (nodeB == tail) { break; } nodeB = nodeB.next; } if (nodeA.next == tail) { break; } nodeA = nodeA.next; nodeB = nodeA.next; } } private void swap(Node nodeA, Node nodeB) { E temp = nodeA.data; nodeA.data = nodeB.data; nodeB.data = temp; } @Override public List subList(int fromIndex, int toIndex) { //0 <= fromIndex <= toIndex <= size - 1 [fromIndex,toIndex] if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) { throw new IllegalArgumentException("must 0 <= fromIndex <= toIndex <= size - 1"); } linkedSinglyList list = new linkedSinglyList<>(); Node nodeA = head; for (int i = 0; i < fromIndex; i++) { nodeA = nodeA.next; } Node nodeB = head; for (int i = 0; i < toIndex; i++) { nodeB = nodeB.next; } Node p = nodeA; while (true) { list.add(p.data); if (p == nodeB) { break; } p = p.next; } return list; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append('['); if (isEmpty()) { sb.append(']'); } else { Node p = head; while (true) { sb.append(p.data); if (p == tail) { sb.append(']'); break; } sb.append(','); sb.append(' '); p = p.next; } } return sb.toString(); } @Override public Iterator iterator() { return new linkedSinglyListIterator(); } class linkedSinglyListIterator implements Iterator { private Node cur = head; @Override public boolean hasNext() { return cur != null; } @Override public E next() { E ret = cur.data; cur = cur.next; return ret; } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)