LinkedList封装
2018-12-28 08:03:38来源:博客园 阅读 ()
LinkedList简单的封装
package com.cn.test.jihe.LinkedList; import java.util.NoSuchElementException; public class LinkedList { // 头结点 Node<Object> first; // 尾指针 Node<Object> last; private int size; // 记录要插入的元素的总数 LinkedList() { } /** * 将指定元素添加到此列表的结尾。 * * @param obj * @return insert */ boolean add(Object obj) { linkLast(obj); return true; } private void linkLast(Object obj) { Node l = last; Node<Object> newNode = new Node<Object>(l, obj, null); last = newNode; // 记录下次要插入的前驱节点 if (l == null) { first = newNode; } else { l.next = newNode; } size++; } /** * 在此列表中指定的位置插入指定的元素。 * * @throws Exception * insert */ void add(int index, Object element) throws Exception { // 判断要插入的位置 rangeCheckIndex(index); // 循环遍历要插入的位置 insertElement(index, element); size++; } private void insertElement(int index, Object element) { int count = 0; Node temp = first; // 在头部进行插入 if (index == 0) { if (temp != null) { Node newNode = new Node(null, element, temp); temp.prev = newNode; first = newNode; } else { Node tempLast = last; Node newNode = new Node(tempLast, element, null); last = newNode; first = newNode; } return; } // 在尾部进行插入 if (index != 0 && index == size) { Node tempLast = last; Node newNode = new Node(tempLast, element, null); last = newNode; tempLast.next = newNode; return; } // 不是在头部或者尾部进行插入 while (temp != null) { // if (count == index) { // 找到要插入的位置 temp这个节点表示要插入的节点的位置 Node newNode = new Node(temp.prev, element, null); newNode.prev.next = newNode; temp.prev = newNode; newNode.next = temp; } temp = temp.next; count++; } } private void rangeCheckIndex(int index) throws Exception { if (index < 0 || index > size) throw new Exception("下标越界"); } /** * 返回列表中指定的元素 * * @param index * @return * @throws Exception * select */ Object get(int index) throws Exception { rangeCheckOut(index); Node temp = first; int count = 0; while (temp != null) { if (count == index) { return temp.item; } count++; temp = temp.next; } return null; } /** * 返回此列表的第一个元素。 * * @throws Exception */ Object getFirst() throws Exception { Node temp = first; if (temp == null) { throw new Exception("该集合没有元素"); } return temp.item; } /** * 返回最后一个元素 * * @return * @throws Exception * */ Object getLast() throws Exception { Node temp = last; if (temp == null) { throw new Exception("该集合没有元素"); } return temp.item; } /** * 返回此列表中首次出现的指定元素的索引,如果此列表中不包含该元素,则返回 -1。 * * @param o * @return */ public int indexOf(Object o) { int count = 0; Node temp = first; if (o == null) { while (temp != null) { if (null == temp.item) { return count; } count++; temp = temp.next; } } else { while (temp != null) { if (o.equals(temp.item)) { return count; } count++; temp = temp.next; } } return -1; } /** * * 返回此列表中最后出现的指定元素的索引, 如果此列表中不包含该元素,则返回 -1。 */ public int lastIndexOf(Object o) { int index = size - 1; if (null == o) { for (Node temp = last; temp != null; temp = temp.prev) { if (null == temp.item) { return index; } index--; } } else { for (Node temp = last; temp != null; temp = temp.prev) { if (o.equals(temp.item)) { return index; } index--; } } return -1; } public int size() { return size; } private void rangeCheckOut(int index) throws Exception { if (index < 0 || index >= size) { throw new Exception("下标越界" + index); } } /** * 删除 获取并移除此列表的头(第一个元素)。 * * @throws Exception */ Object remove() throws Exception { if (first == null) { throw new Exception("链表为空"); } Node oldNode = first; first = oldNode.next; if (first != null) { first.prev = null; } else { last = null; } size--; return oldNode.item; } /** * 移除此列表中指定位置处的元素。 * * @param index * @throws Exception */ Object remove(int index) throws Exception { // 判断长度是否超限 rangeCheckOut(index); // 确认要删除的节点 Node oldNode = getIndexNode(index); unLinkNode(oldNode); return oldNode.item; } /** * remove(Object o) 从此列表中移除首次出现的指定元素(如果存在)。 */ boolean remove(Object o) { // 列表是否有该元素 , 如果有返回该节点 Node oldNode = checkeElement(o); if (oldNode != null) { unLinkNode(oldNode); return true; } return false; } /** * 移除并返回此列表的第一个元素 * * @return * @throws Exception */ Object removeFirst() throws Exception { if (first == null) { throw new Exception("linkedList is null"); } Object oldValue = first.item; first = first.next; if (first == null) { last = null; } else { first.next.prev = null; } size--; return oldValue; } /** * 移除最后一个元素 * * @return */ public Object removeLast() { Node l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * 将此列表中指定位置的元素替换为指定的元素。 * * @param index * @param element * @return * @throws Exception */ public Object set(int index, Object element) throws Exception { // 判断要插入的索引的位置 rangeCheckOut(index); // 获取要插入位置的节点 Node indexNode = getIndexNode(index); Object oldValue = indexNode.item; indexNode.item = element; return oldValue; } /** * 返回以适当顺序(从第一个元素到最后一个元素)包含此列表中所有元素的数组 * * @return */ public Object[] toArray() { Object[] result = new Object[size]; int count = 0; for (Node temp = first; temp != null; temp = temp.next) { result[count] = temp.item; count++; } return result; } private Object unlinkLast(Node l) { final Object element = l.item; Node prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) { first = null; } else { last.next = null; } size--; return l.item; } private Node checkeElement(Object o) { if (o == null) { // 循环遍历链表 for (Node temp = first; temp != null; temp = temp.next) { if (null == temp.item) { return temp; } } } else { for (Node temp = first; temp != null; temp = temp.next) { if (o.equals(temp.item)) { return temp; } } } return null; } /** * 取消链表节点之间的关系 * * @param oldValue */ private void unLinkNode(Node oldNode) { Node beforeNode = oldNode.prev; Node afterNode = oldNode.next; if (beforeNode == null) { // 要删除的节点是头节点 first = afterNode; afterNode.prev = null; } if (afterNode == null) { // 要删除的节点是尾节点 last = beforeNode; beforeNode.next = null; } if (beforeNode != null && afterNode != null) { // 删除的非头节点和非尾节点 修改指针的位置 beforeNode.next = afterNode; afterNode.prev = beforeNode; } size--; } /** * 找到要删除的节点 * * @param index */ private Node getIndexNode(int index) { if (index < (size >> 1)) { // 删除节点的位置为链表的前半段 Node firstNode = first; for (int i = 0; i < index; i++) { firstNode = firstNode.next; } return firstNode; } else { Node lastNode = last; for (int i = --size; i > index; i--) { lastNode = last.prev; } return lastNode; } } private Object removeAfterNode(int index) { // 首先迭代 int count = 0; for (Node temp = first; temp != null; count++) { if (index == count) { // 找到要删除的节点进行删除 Object oldValue = temp.item; Node previous = temp.prev; Node after = temp.next; previous.next = after; size--; return oldValue; } temp = temp.next; } return null; } /** * 采用双链表 */ private static class Node<Object> { Object item; Node<Object> next; // 下一个节点 Node<Object> prev; // 前驱节点 Node(Node<Object> prev, Object element, Node<Object> next) { this.item = element; this.next = next; this.prev = prev; } Node(Object item) { this.item = item; } } }
testCast
/* LinkedList list = new LinkedList(); list.add(1); list.add(1, 2); list.add(2); list.add(3); list.add(2,8); list.add(0,4); list.add(1,2); list.add(0,8); list.add(2); list.add(5); System.out.println(list.size()); // System.out.println(list); Object first = list.getFirst(); System.out.println("fist=" + (int)first); Object last = list.getLast(); System.out.println("last=" + (int)last); int indexOf = list.indexOf(10); System.out.println("indexof=" + indexOf); int lastIndexOf = list.lastIndexOf(100); System.out.println("lastIndex=" + lastIndexOf); LinkedList list2 = new LinkedList(); list2.add(2); Object remove = list2.remove(); for (int i=0; i<list.size();i++) { System.out.print("i=" + (int)list.get(i) + " "); } Object remove = list.remove(0); System.out.println("remove=" + remove); list.add(130); for (int i=0; i<list.size();i++) { System.out.print("i=" + (int)list.get(i) + " "); } System.out.println(); list.remove(new Integer(4)); for (int i=0; i<list.size();i++) { System.out.print("j1=" + (int)list.get(i) + " "); } System.out.println(); list.add(0,89); list.add(8,129); list.removeFirst(); list.removeFirst(); System.out.println("------------------"); for (int i=0; i<list.size();i++) { System.out.print("j2=" + (int)list.get(i) + " "); } */ LinkedList list2 = new LinkedList(); list2.add(new String("a")); list2.removeFirst(); list2.add(new String("b")); // list2.add(new String("c")); // list2.remove(new String("c")); list2.removeLast(); list2.add(new String("c")); list2.add(new String("d")); list2.removeLast(); // list2.removeLast(); list2.add(new String("f")); list2.set(0, new String("222")); list2.add(1, new String("14")); //list2.removeLast(); for (int i=0; i<list2.size();i++) { System.out.print("j3=" + (String)list2.get(i) + " "); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 数据结构:用实例分析ArrayList与LinkedList的读写性能 2020-06-04
- SpringCloud异常处理统一封装我来做-使用篇 2020-05-23
- JAVA连载117-反射的应用与打破封装新 2020-05-23
- LinkedList源码(add方法) 2020-05-19
- 错题记录——关于Java中private的用法(类与封装) 2020-05-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash